Theory of computations

An Introduction to formal language and automata 6th edition.

Chapter 6: Simplification of context free grammars and normal forms.

Solve the following questions.

Please solve it clearly

use Keyboard not hand writtin answers.

Thank you.

2. Do Exercise 1 of Section 6.3 at page 180. 1. Use the CYK algorithm to determine whether the strings abb, bbb, aabba, and abbbb are in the language generated by the grammar in Example 6.11. EXAMPLE 6.11 Determine whether the string w aabbb is in the language generated by the grammar S AB A BBla, B ABIb First note that w11 a, so Vil is the set of all variables that immediately derive a, that is, Vii {A). Since w22 E a, we also have V22 {A) and, similarly, {A), V22 Now we use (6.8) to get {A: A BC, B e V11, CE I/22) 12 Since Vii (A) and Va {A), the set consists of all variables that occur on the left side of a production whose right side is AA. Since there are none, Vi2 is empty. Next, {A A. BC, B E V22, CE V33), so the required right side is AB, and we have Vas {S, B). A straight- forward argument along these lines then gives 12 V23 {S, B), 24 {S, B) 15 so that w EL(G)