Question

4. Consider two grammars Gi and G2 over the alphabet (a, b], with respective start symbols E and I and specified by the respective sets of production rules below: EFab (a) Do the two grammars generate the same language? If they do, briefly argue why. If they do not, provide a counter-example, that is, a word generated by one, but not by the other (b) The grammar G2 is unnecessarily complicated. Write a grammar that generates the same language generated by G2 but uses only one non-terminal symbol

Answer 1

(a)

• No. These two grammars do not generate the same language. The grammar G₂ can generate string "ab" but grammar G₁ cannot generate "ab".
• For grammar G₁, minimum length is 4 for the string generated by this grammar and that string is "abab".
• 
  "No. These two grammars do not generate the same language. The grammar G2 can generate string ""ab"" but grammar G1 cannot generate ""ab"". For grammar G1, minimum length is 4 for the string generated by this grammar and that string is ""abab"" Thus, string ""ab"" cannot be generated by grammar G1 and thus these two grammar do not generate the same language. (b) The grammar that generates the same language as generated by G2 can be written as: G\rightarrow Gab
  
• For grammar G₂, minimum length is 2 for the string generated by this grammar and that string is "ab".
• 
• Thus, string "ab" cannot be generated by grammar G₁ and thus these two grammar do not generate the same language.

(b)

• The grammar that generates the same language as generated by G₂ can be written as:
• $G\rightarrow Gab | \epsilon$
• Strings generated from this grammar G are "ab", "abab", "ababab" and many more which can be generated by grammar G₂ also.
• Thus, this grammar generates the same language and uses only one non-terminal symbol.