Introduction to Computer Theory

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

{aⁿb^ma^mbⁿ| m > 1, n > 1 }

is context-free.

2. Show that the language

{aⁿbⁿcⁿdⁿ 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

a^xb^ya^z, where x,y,z=1 2 3….and x+z=y

={abbbba abbbbbbaa aabbbbbba…}

3(a). Find CFG for the language:

L₂= (bb)*a

3(b). Find CFG for the language L₂*

4. Show that the language

{bbaⁿbaⁿ⁺¹| 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