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$ 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$ 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$ 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$ 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?

  • 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$ 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$ 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.