Question 3: Considering the following Context-free Grammar : S → ASB | AB A → aAS | aA | a B → SbS | bS | Sb | b | aAS |
Posted: Mon Jun 06, 2022 12:24 pm
Question 3: Considering the following Context-free Grammar
: S → ASB | AB
A → aAS | aA | a
B → SbS | bS | Sb | b | aAS | aA | a | bb
where A, B, S are variables and a, b are terminals
a) List down all generating symbols and if needed, eliminate all
non-generating (useless) symbols. Then list down all reachable
symbols and if needed, eliminate all non-reachable (useless)
symbols.
b) Apply the two conversion steps on the resulting Grammar of
part (a) to bring it into Chomsky Normal Form.
: S → ASB | AB
A → aAS | aA | a
B → SbS | bS | Sb | b | aAS | aA | a | bb
where A, B, S are variables and a, b are terminals
a) List down all generating symbols and if needed, eliminate all
non-generating (useless) symbols. Then list down all reachable
symbols and if needed, eliminate all non-reachable (useless)
symbols.
b) Apply the two conversion steps on the resulting Grammar of
part (a) to bring it into Chomsky Normal Form.