In my homework we're given the following problem: Determine whether the context-free language described by the following grammar is regular, showing all the reasoning steps:

S -> T T | U

T -> 0 T | T 0 | #

U -> 0 U 0 0 | #.

My teacher says the pound sign (#) is just a delimiter that is in the alphabet and not epsilon.

I understand the order of operations here is to go from CFG --> CFL --> RL (if possible).
My problem is that I don't know how to provide a CFL given a CFG, and further, determine whether a CFL is regular.

So to ask the questions:

how do you provide a context-free language (CFL) given a context-free grammar (CFG)?

how do you determine if a context-free language (CFL) is also a regular language (RL)?

  • 1
    $\begingroup$ Have you tried actually writing down a few of the words in this language? $\endgroup$ – Karolis Juodelė Nov 3 '13 at 8:32
  • $\begingroup$ Yes. But I can't determine what numbers of 0s are valid. It seems like any number of 0s is valid. $\endgroup$ – RebelOfBabylon Nov 3 '13 at 8:49
  • 1
    $\begingroup$ First of all, $L(S)$ this is an union of two non intersecting languages. Words generated by $S \to TT$ have two #s and words generated by $S \to U$ have only one #. So deal with them separately. $\endgroup$ – Karolis Juodelė Nov 3 '13 at 8:54
  • $\begingroup$ Okay, I think I have been able to come up with some strings. ##(by TT), # (U), 0#00 (U), 0#0# (TT -> 0T0T), 0##0 (TT -> 0TT0), 00#0000 (U -> 0U00), 0#00#0 (TT -> 0TT0 -> T00T). $\endgroup$ – RebelOfBabylon Nov 3 '13 at 10:16

$$\begin{align}L(T) &= \{0^*\#0^*\} \\ L(U) &= \{0^n\#0^{2n}\} \\ L(S) &= L(T) \circ L(T) \cup L(U) \end{align}$$ Where $\circ$ is concatenation. Clearly, $L(U)$ is not regular. What does that say about $L(S)$? How does $L(T)$ affect this?

| cite | improve this answer | |
  • 1
    $\begingroup$ Where "cearly" follows from several answers to our reference question. $\endgroup$ – Raphael Nov 3 '13 at 15:27
  • $\begingroup$ Okay. So Regular Languages are closed under concatenation, complementation, and union. L(T) is regular, L(T) • L(T) is regular, and so is L'(T) (complement). L(U) is non-regular. I'm trying to think of how this could be used for a proof. (non-regular language) U (regular language). Is the result necessarily regular or non-regular? I know I'm not getting some fundamental things here. I appreciate the help walking me through this. $\endgroup$ – RebelOfBabylon Nov 4 '13 at 2:41
  • $\begingroup$ In general $\text{CFL} \cup \text{RL}$ could turn out to be either. Take a proof that $L(U)$ is context free (say, using pumping lemma). Then see if any words in $L(T) \circ L(T)$ make that proof invalid. As an exercise, do the same for the language $L(T) \cup L(U)$. $\endgroup$ – Karolis Juodelė Nov 4 '13 at 16:54

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.