Question

Consider the following grammar

S -> A M
M -> S
   |
A -> a E
   | b A A
E -> a B
   | b A
   |
B -> b E
   | a B B

Show a derivation for the string a b a a. Start with

S => A M
  => ...

and in each step replace one nonterminal by the right-hand side of a grammar rule until you end up with the symbols a b a a on a line by itself. Underline the nonterminal you are expanding and write the expanded line underneath.

Answer 1

The above problem is all about deriving a given string from the given grammar.

we can derive the strings from the grammar by substituting the terminals in place of non terminals .