Question

For a given grammar below, G = ( {S, A, B}, {a, b}, S, P ) with productions S ->1 AB | bbbB, A ->2 b | Ab, B ->3 a..

1. Show the grammar G is ambiguous.
2. Give language L that is generated by G, L = L(G), in a formal expression (including a regular expression).
3. Construct an unambiguous grammar that is equivalent to G.

Answer 1

The grammar G is ambiguous as the string 'bbbbba' can be derived in two distinct ways. The language L generated by G can be expressed as the regular expression L = b*a*.

Step-by-step explanation:

Show that Grammar G is Ambiguous

To prove that the given context-free grammar G is ambiguous, we need to find at least one string that can have more than one parse tree or derive it in more than one way. Consider the string 'bbbbba'. It can be derived in two different ways:

S → AB → Abba → bAbba → bbbbBa → bbbbaa

S → bbbB → bbbBa → bbbbba

Since there are two different derivation sequences for 'bbbbba', the grammar G is ambiguous.

Language L Generated by G

The language L(G) includes strings made up of 'b's followed by 'a's. Formally, this can be written as a regular expression: L = b*a*. This regular expression denotes zero or more 'b's followed by zero or more 'a's.

Construct an Unambiguous Grammar Equivalent to G

An unambiguous grammar that is equivalent to G can be defined as:

S → A'B | bbbB

A' → bA''

A'' → bA'' | ε

B → aB | a

This grammar generates the same language as G but without the ambiguity, for each string in the language, there is only one parse tree.