Construct CFG without ϵ production from: S → a | Ab | aBa A → b | ϵ B → b | A


Given,
S → a | Ab | aBa
A → b | ϵ
B → b | A
If we observe carefully, then not only A have ϵ production but even B also B also indicates ϵ production.
A → ϵ
Straight forward for B → A → ϵ
Now, Apply the method of replacement,
S → Ab
if A → ϵ then
S → b
If B → ϵ
S → aa for s → aBa
∴ S → a | Ab | b | aa | aBa
& A → b
B → b
Finally the rules are,
S → a | Ab | b | aa | aBa
A → b
B → b

No comments

Dear Members, Thanks for Your Comments. We must be reply your comment answer as soon as possible. Please Stay with us.....

Theme images by ideabug. Powered by Blogger.