**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 |

**Answer:** NFA:

| d | 0 | 1 |

-> | A |
0 | {B, C} |

| B |
{D} | {E} |

* | C |
0 | {E} |

| D |
0 | {B, C} |

| E |
{C} | 0 |

**Date:** Mar. 15, 2001.

**Question:**
What are the equivalence classes of R_{L} induced on ={0,1}, where *L* is defined by the regular
expession **a(a+b)*b**? What is the index of R_{L}?
**Answer:**
*/R_{L} = {C_{0}, C_{1},
C_{2}, C_{3} }, where

C_{0} = **e**,

C_{1} = **a(a+b)*b**,

C_{2} = **a(a+b)*a**,

C_{3} = **b(a+b)***.

The index of R_{L} is 4.

**Date:** Mar. 22, 2001.

**Question:**
Design a CFG for the language
{a^{n}b^{n}c^{m}d^{m}}. Show the
derivation trees of the string abcd in this grammar.
**Answer:**

S -> AB
A -> aAb | ab
B -> cBd | cd

The derivation tree:
S
/ \
A B
/\ / \
a b c d

**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 -> C_{a}BC
B -> C_{b}B | b
C -> C_{a}C_{b}
C_{a} -> a
C_{b} -> b

Equivalent grammar in CNF:
S -> C_{a}D
D -> BC
B -> C_{b}B | b
C -> C_{a}C_{b}
C_{a} -> a
C_{b} -> b

**Date:** Apr. 10, 2001.

**Question:**
Give CFG's for the following languages:

a) *L*_{a} =
{a^{j}b^{j}c^{k} | j > 0, k > 0}

b) *L*_{b} =
{a^{j}b^{k}c^{k} | j > 0, k > 0}
**Answer:**

a) *G*_{a}: S -> AB, A -> aAb | ab, B -> cB | c

b) *G*_{b}: S -> AB, A -> aA | a, B -> bBc | bc

**Date:** Apr. 17, 2001.

**Question:**
Design a Turing Machine to accept 0*1*.
**Answer:**

d | 0 | 1 | B |

q_{0} | (q_{0},0,R) | (q_{1},1,R) | (q_{2},B,R) |

q_{1} | - | (q_{1},1,R) | (q_{2},B,R) |

q_{2} | - | - | - |

F = {q_{2}}

**Date:** May 10, 2001.

**Question:**
Define the language of the problem "Does DFA *M* accept the
string *w*?" Is this problem decidable?
**Answer:**
*L*= { <*M*,*w*> | *M* accepts
*w*}.

There is an algorithm to determine if a DFA *M* accepts
the string *w*. The algorithm halts in |*w*| steps, with Yes
or No answer. Therefore, the language *L* is recursive, and the
problem is decidable.