# CS 476 Quizes

1. Date: Feb. 20, 2001.
Question: Convert the following NFA w/epsilon-moves to an equivalent NFA.
 d 0 1 e -> A 0 {B} 0 B {D} 0 {C} * C 0 {E} 0 D 0 {B} 0 E {C} 0 0

 d 0 1 -> A 0 {B, C} B {D} {E} * C 0 {E} D 0 {B, C} E {C} 0

2. Date: Mar. 15, 2001.
Question: What are the equivalence classes of RL induced on ={0,1}, where L is defined by the regular expession a(a+b)*b? What is the index of RL?

Answer: */RL = {C0, C1, C2, C3 }, where
C0 = e,
C1 = a(a+b)*b,
C2 = a(a+b)*a,
C3 = b(a+b)*.
The index of RL is 4.

3. Date: Mar. 22, 2001.
Question: Design a CFG for the language {anbncmdm}. Show the derivation trees of the string abcd in this grammar.

```S -> AB
A -> aAb | ab
B -> cBd | cd
```
The derivation tree:
```       S
/ \
A   B
/\  / \
a  b c  d
```

4. Date: Mar. 27, 2001.
Question: Convert the following grammar into CNF.
```S -> aBC
B -> bB | b
C -> D
D -> ab
```

Answer: After the removal of unit productions:

```S -> aBC
B -> bB | b
C -> ab
D -> ab
```
After the removal of useless symbols:
```S -> aBC
B -> bB | b
C -> ab
```
After replacing terminal with new variables:
```S -> CaBC
B -> CbB | b
C -> CaCb
Ca -> a
Cb -> b
```
Equivalent grammar in CNF:
```S -> CaD
D -> BC
B -> CbB | b
C -> CaCb
Ca -> a
Cb -> b
```

5. Date: Apr. 10, 2001.
Question: Give CFG's for the following languages:
a) La = {ajbjck | j > 0, k > 0}
b) Lb = {ajbkck | j > 0, k > 0}

a) Ga: S -> AB, A -> aAb | ab, B -> cB | c
b) Gb: S -> AB, A -> aA | a, B -> bBc | bc

6. Date: Apr. 17, 2001.
Question: Design a Turing Machine to accept 0*1*.