Consider the language L amb3nc2ndp p m and m n 1 show you

Consider the language L = {amb3nc2ndp : p > m, and m, n 1}. (show your work) (a) What is the shortest string in L? (b) Write a context-free grammar to generate L.

Solution

SOLUTION:

(a) The shortest string in L is i.e.(m=n=1,d=2) = abbcccdd   

(b) G = ({S, X, Y, a, b, c, d}, {a, b, c, d}, R, S),

R = { S aXdd
X Xd
X aXd
X bbYccc
Y bbYccc
Y }

or

R = { S aSd
S Sd
S aMdd
M bbccc
M bbMccc }