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, 2015 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, 2015 at 20:21
  • $\begingroup$ Rather than close the question, it could be nice to collect different proofs. $\endgroup$
    – babou
    May 26, 2015 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, 2015 at 20:34
  • $\begingroup$ @babou Feel free to provide such at the duplicate question. $\endgroup$
    – Raphael ♦
    May 27, 2015 at 6:51

0

Reset to default

Browse other questions tagged or ask your own question.