0
$\begingroup$

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.

$\endgroup$
  • 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
2
$\begingroup$

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.

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