Can we find grammar for every CFL without $ε $ with these productions

72 Views Asked by At

So we have a CFL that doesn't have $ε$ and I have to prove that we can find a grammar for that language with all productions like this $A->BCD$ or $A->a$. I'm thinking about dividing $A->BCD$ into $A->BC$ and $C->CD$ so the grammar is a Chomsky grammar, and it is said that every CFL without $ε$ can be represented by a Chomsky grammar. But I can't quite wrap my head around it, also we can try to propose a counterexample but I am not sure if that is possible.

Thank you!

1

There are 1 best solutions below

1
On BEST ANSWER

How would you generate a sentence with exactly two symbols? If you have no ε productions, the shortest sentence produced by $S\to ABC$ has length three.