anaon12
anaon12

Reputation: 27

Converting a CFG into Chomsky Normal form

  1. Using the Pumping Lemma for Regular Languages, show that the

    language L = { ai, bj ck | i, j, k are non-negative integers, and i=j or i=k }

is not regular

  1. Design CFG for the language above

This is what I came up with

Answer: G = (V,,R, S) with set of variables V = {S,W,X, Y,Z},
where S is the start variable; set of terminals  = {a, b, c}; and rules
S → XY | W
X → aXb | e
Y → cY | e
W → aWc | Z
Z → bZ | e

Now I have to convert the above CFG into chomsky normal form which I am having trouble with...any help?

Upvotes: 1

Views: 185

Answers (0)

Related Questions