0
$\begingroup$

This question already has an answer here:

I have the following problem to solve:

Show that if G is a context-free grammar and Σ consists of just one terminal symbol, then L(G) is regular.

It is problem 4.26 from the book "Formal models of computation" by Arthur Fleck.

Do you have any ideas or solutions?

|cite|improve this question
$\endgroup$

marked as duplicate by Hendrik Jan, David Richerby, Ran G., Luke Mathieson, Juho May 27 '15 at 6:11

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ What did you try? Where did you get stuck? $\endgroup$ – David Richerby May 26 '15 at 19:57
  • 1
    $\begingroup$ Yes, we have ideas, but it may depend on what you know. My own inclination is to use the Chomsky–Schützenberger representation theorem. $\endgroup$ – babou May 26 '15 at 20:21
  • $\begingroup$ Rather than close the question, it could be nice to collect different proofs. $\endgroup$ – babou May 26 '15 at 20:22
  • $\begingroup$ I tried induction on the length of the derivation, but I got an infinite union of regular languages. I don't know the Chomsky–Schützenberger representation theorem. I checked out this post: cs.stackexchange.com/questions/40791/… but I couldn't understand how to prove that the union of Lw = L2 and it is a finite union. Any suggestions will be very appreciated. $\endgroup$ – Dimitar Uzunov May 26 '15 at 20:34
  • $\begingroup$ @babou Feel free to provide such at the duplicate question. $\endgroup$ – Raphael♦ May 27 '15 at 6:51