# Determining whether a context-free language (CFL) described by a given grammar is regular (RL)

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.

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

• Have you tried actually writing down a few of the words in this language? Nov 3 '13 at 8:32
• Yes. But I can't determine what numbers of 0s are valid. It seems like any number of 0s is valid. Nov 3 '13 at 8:49
• 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. Nov 3 '13 at 8:54
• 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). 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?
• 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)$. Nov 4 '13 at 16:54