Question

Consider the language L1 over alphabet Σ = { 0, 1 } where the production rules for L1 are as follows:

S → TT
S → U
T → 0T
T → T0
T→ 1
U → 0U00
U → 1
Q → λ
P → QU

Transform this grammar into Chomsky Normal Form, consistent with the CNF specification in the Quick Reference, and using only Variables { S, T, U, V, W, X }.

Implement that CNF grammar in JFLAP

Answer 1

Here, we have Language L1 as:

Variables = { S, T, U ,V, W, X}

Terminals = { 0, 1 }

Start Symbo = S

S -> TT

S -> U

T -> 0T

T -> T0

T -> 1

U -> 0U00

U -> 1

Q ->

P -> QU

Now, we know that :

CNF stands for Chomsky normal form. A CFG(context free grammar) is in CNF(Chomsky normal form) if all production rules satisfy one of the following conditions:

• Start symbol generating ε. For example, A → ε.
• A non-terminal generating two non-terminals. For example, S → AB.
• A non-terminal generating a terminal. For example, S → a.

Step 1: Here, there is a NULL value , we will remove  .

S -> TT

S -> U

T -> 0T

T -> T0

T -> 1

U -> 0U00

U -> 1

P -> QU

P -> U

Now , again,

S -> TT

T -> 0T

T -> T0

T -> 1

U -> 0U00

U -> 1

P -> QU

s -> U

S -> 1

unit removal is completed. Select proceed to begin removing useless production.

Let X -> 0

S ->TT

S -> U

T -> XT

T -> TX

T -> 1

U -> xUxx

U -> 1

P -> U

again,

Now let W -> XX, V -> UXX

S -> TT

S -> U

S -> 1

T -> XT

T -> TX

T ->  1

U - > XV

U -> 1

V -> UXX

W -> XX

X -> 0

Hence , final CNF grammar is

S ->TT

S -> XV

T -> XT

T ->1

U -> XV

U ->1

V -> UW

W -> XX

X -> 0

Now this is in Chomsky Normal Form (CNF).