# 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.

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

• Have you tried actually writing down a few of the words in this language? – Karolis Juodelė 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. – RebelOfBabylon 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. – Karolis Juodelė 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). – RebelOfBabylon Nov 3 '13 at 10:16

## 1 Answer

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

• Where "cearly" follows from several answers to our reference question. – Raphael Nov 3 '13 at 15:27
• 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. – RebelOfBabylon Nov 4 '13 at 2:41
• 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)$. – Karolis Juodelė Nov 4 '13 at 16:54