For this assignment the prescribed book used is: Introduction to Computer Theory, Second Edition
Author: Daniel I.A Cohen.

1. Draw a deterministic PDA to show that the language
{anbmambn| m > 1, n > 1 }

is context-free.

2. Show that the language
{anbncndn for n=1 2 3 ....}= {abcd aabbccdd} is non-context-free. Use a pumping lemma.

3. Find CFG for this language:

All words of the form

axbyaz, where x,y,z=1 2 3....and x+z=y

={abbbba abbbbbbaa aabbbbbba...}

3(a). Find CFG for the language:
L2= (bb)*a

3(b). Find CFG for the language L2*

4. Show that the language
{bbanban+1| n > 0 }

is context-free by building a PDA that accepts precisely this language.

5. Decide whether or not the following grammars generate any words using the algorithm of theorem 42.

SàaSa | bSb. Show every step in your solution.

6. For the following grammar, decide whether the language they generate is fine or infinite using the algorithm in theorem

44(page. 403)

SàXY | bb

XàYY

YàXY | SS. Show every step in your solution.

7. For the following grammar and target strings, decide whether or not the word is generated by the grammar using the CYK algorithm

Sà SS x=abba

Sàa

Sàbb