Is the following true or false? Why?

Let L be a context-free language with $\epsilon\notin$ L. Then there is $\epsilon$-free grammar $G=(V,\Sigma, P,S )$ with $L (G) = L$, so all production rules are of form $A \to BCD$ or $A\to a$ with $A, B, C, D \in V$ and $a\in$ $\Sigma$.

I don't know normal forms for context-free languages. Just the CNF for regular ones. Trying a few small examples don't gives me a generally valid response, if there are really always production rules of this form.

  • 2
    $\begingroup$ Hello! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered. $\endgroup$ – dkaeae Feb 27 '19 at 18:03
  • $\begingroup$ I am not sure if there are products of form A-> BC possible. $\endgroup$ – user101037 Feb 27 '19 at 18:20
  • 2
    $\begingroup$ Your title is way too general. $\endgroup$ – Yuval Filmus Feb 27 '19 at 18:21
  • 1
    $\begingroup$ @user11122042 Welcome to Computer Science! I did some minor formatting of the question. I also moved your comment to the question since it is generally expect of OP to show proof of work in the question. I did this since you are a complete newcomer. Have you read how to ask a good homework question?? $\endgroup$ – John L. Feb 27 '19 at 22:05
  • 1
    $\begingroup$ Please choose one StackExchange community to ask a question. Asking the same question on two different sites is not fair to potential responders, who will not see that the question has already been answered on another site. If you feel you chose badly because the question remains unanswered after a couple of days, you can delete the question and ask it on a different site, if there is another appropriate site. $\endgroup$ – rici Feb 27 '19 at 22:57

Hint, can the production rules of that form generate a word of length 2? Is there a context-free language that contains a word of length 2?

  • $\begingroup$ the Language L={aa} is regular, so it is contextual free. The productions would be S-> Aa, A->a. Does that mean, that the statement is false? $\endgroup$ – user101037 Feb 27 '19 at 22:39
  • $\begingroup$ Correct. The statement is false. $\endgroup$ – John L. Feb 27 '19 at 22:42
  • $\begingroup$ But what is about the grammar : S-> ABC, A->$\epsilon$, B->a, C-> a. It looks like this form and contains just the word aa $\endgroup$ – user101037 Feb 28 '19 at 12:41
  • $\begingroup$ Is that grammar $\epsilon$-free? Hm, it looks like the title I made is somewhat misleading. $\endgroup$ – John L. Feb 28 '19 at 13:08
  • $\begingroup$ The grammar is not $\epsilon$ free, but the language is, isn't it? Or is the given grammar not context-free? $\endgroup$ – user101037 Feb 28 '19 at 13:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy