Question

(3) Consider the following three languages over the alphabet Σ default i,j, k, are non-negative integers (can be 0): (a,b,c,d), where by One of these is not a CFL; the other two are CFLs. Give context-free grammars for the two that are CFLs, and a CFL Pumping Lemma proof for the one that is not a CFL. (You need not prove your grammars correct, but their plan should be clear. (6+6+18 30 pts., for 74 total on the set)

Answer 1

• L1 is context free
  

Grammar

S -> AB
A -> aAb | bA | b
B -> cBd | dB | d

Explanation

• A is for a's and b's -- i < j
• C is for c's and d's -- k < l

• L2 is not context free

• L3 is context free

Grammar

S -> aSd | Sd | Ad
A -> bAc | Ac | c

Explanation

• i < l: for a's and d's
• j < k: for b's and c's

Please post another question for Pumping Lemma proof on L₂