CODEWITHSUNDEEP
context-free-grammarchomsky-normal-form
alkokarko
alkokarko

Reputation: 85

How to solve this Chomsky Form

S → aSab | ABB | BB

A → baab | BABB | AaA

B → bAaBa | bb | b

I started solving it but it seems I just kept on adding new rules to keep up, can someone please explain how to do this one.

Upvotes: 0

Views: 125

Answers (1)

blurry
blurry

Reputation: 114

This is the resulting grammar in Chomsky normal form:
defined by a 4-tuple of set of non-terminal symbols, set of terminal symbols, rules and the start symbol, respectively.

G = ({S,A,B,<Sab>,<ab>,<BB>,<aab>,<ABB>,<aA>,<AaBa>,<aBa>,<Ba>,a',b'},{a,b},R,S)

R =
S → a'<Sab> | A<BB> | BB
A → b'<aab> | B<ABB> | A<aA>
B → b'<AaBa> | b'b' | b
<Sab> → S<ab>
<ab> → a'b'
<BB> → BB
<aab> → a'<ab>
<ABB> → A<BB>
<aA> → a'A
<AaBa> → A<aBa>
<aBa> → a'<Ba>
<Ba> → Ba'
a' → a
b' → b

Feel free to rename the non-terminals in angle brackets <> by one-character capital symbols as you feel appropriate (they do mean a single non-terminal character), I find this more suitable.

Upvotes: 1

Related Questions