I am preparing for my exam in Formal languages and Automata theory and I'm looking at some old exam questions right now. I need help with the following question:

For each of the following languages answer whether it is regular, context-free but not regular, or not context-free. A brief, informal explanation is sufficient.

$$ L_3 = \left\{ w \in \{a,b,c,d\}^* \Bigg| \begin{array}{l} \text{\(w\) does not have a substring \(aba\),} \\ \text{each \(a\) in \(w\) is immediately followed by \(b\),} \\ \text{and \(\#c(w)\) is odd} \end{array} \right\} $$ $$ \begin{align} L_4 &= \{ a^ib^jc^ka^ib^l \mid j \gt l \text{ and } i,l,k \gt 0 \} \\ L_5 & \text{ is the image of \(L_4\) under the homomorphism } h:\{a,b,c,d\}^* \to \{0,1,2\}^* \\ & \text{ such that } h(a) = h(b) = 10 \text{ and } h(c) = 210 \text{ and } h(d) = \epsilon \\ L_6 & \text{ is the image of \(L_4\) under the homomorphism } h:\{a,b,c,d\}^* \to \{0,1,2\}^* \\ & \text{ such that } h(a) = h(b) = 210 \text{ and } h(c) = h(d) = \epsilon \\ \end{align} $$

Here is my attempt:

$L_3$ is regular. It's the intersection between 3 regular languages. Regular languages are closed under intersection, so the resulting language is regular. The language where $w$ does not have a substring $aba$ is just the complement of the language $aba$, regular languages are closed under complement, so the resulting language is regular. The language with an odd number of $c$ is regular. Hence the resulting language when taking the intersection between these languages is regular.

$L_4$ is not context-free. When reading the first $a$'s we will push the $a$'s onto the stack. Then we will read the first $b$'s and push them onto the stack. Then we will read the $c$'s. When we now read a second group of $a$'s, we will not be able to compare the number with the first $a$'s, because $b$'s are on the top of the stack and if we pop them then we will not be able to compare the number $b$'s in the beginning and the end. Hence, $L_4$ is not context-free.

$L_5$ is context-free but not regular. The language in question looks like this: $$ 10^{i+j} 210^k10^{i+l} \text{ where } j \gt l \text{ and } i,l, k \gt 0 $$ A grammar can be constructed which generates at least one more $10$ in the beginning of the string than $10$ after $210$.

$L_6$ is regular because it's given by the regular expression: $$ 210^{2i + j + l} \text{ where } 2i+j+l \text{ is any number } \gt 0$$

Is this correct? Note that informal explanations is sufficient in the answer and that no grammars has to be given.


closed as off-topic by D.W., frafl, Luke Mathieson, J.-E. Pin, Juho Oct 30 '13 at 10:12

  • This question does not appear to be about computer science within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    $\begingroup$ This question appears to be off-topic because it is about grading your homework solutions. Please see this related meta discussion. If you want to ask a specific question about a specific part of your attempt, please edit the question accordingly and it may be reopened. $\endgroup$ – D.W. Oct 15 '13 at 17:32

The answers are correct, but when proving that a language is not regular, or not context-free, it is not enough to show that one attempt does not work. You have to use tools like pumping lemma. For context-free languages, there is a version of pumping lemma which should work here: http://en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages

Also it's a detail, but in your last argument, $2i+j+l$ is not any number $>0$, it is at least $5$, since $j>l$ and $i,l,k>0$. So your language is $\{(210)^n : n\geq 5\}$, which is indeed regular.

  • $\begingroup$ Thank you very much. I know but this certain question doesn't require use of the pumping lemma. Thank you again. $\endgroup$ – mrjasmin Oct 14 '13 at 15:00
  • $\begingroup$ You can also use closure properties and known languages which are not regular or not context-free. For the regular case, you can also use Myhill-Nerode (though perhaps not in the exam; exams are stupid). $\endgroup$ – Yuval Filmus Oct 14 '13 at 21:05

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