# Deciding the class of certain languages [closed]

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, JuhoOct 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.

• 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. – D.W. Oct 15 '13 at 17:32

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.