0
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 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