-1
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ Have you tried actually writing down a few of the words in this language? $\endgroup$ Nov 3, 2013 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, 2013 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, 2013 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, 2013 at 10:16

1 Answer 1

0
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Where "cearly" follows from several answers to our reference question. $\endgroup$
    – Raphael
    Nov 3, 2013 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, 2013 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, 2013 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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