Deciding whether a Language is Context-free/Regular/Non Context-Free

Question

I need some help with deciding if a given language is regular, context-free or not context-free.

Lets' say I have the following languages over the alphabet $\mathcal{A} = \{a,b,c,d\}$: $$ \begin{align} L_1 &= \{ w \in \mathcal{A}^* \mid \text{\(\#a(w)\) is even and \(\#b(w) = 1 \mathrel{\mathrm{mod}} 3\) and \(w \not\in \mathcal{A}^* abc \mathcal{A}^* \)} \} \\ L_2 &= \{ w \in \mathcal{A}^* \mid \text{\(\#a(w)\) is even and \(\#b(w) \lt \#c(w)\)} \} \\ L_3 &= \{ w \in \mathscr{A}^* \mid \#a(w) \lt \#b(w) \lt \#c(w) \} \\ \end{align} $$

This is my solution:

$L_1 = L_4 \cap L_5 \cap L_6$ where $$ \begin{align} L_4 &= \{ w \mid \text{\(w\) does not have a substring \(abc\)} \} \\ L_5 &= \{ w \mid \#a(w) \text{ is even} \} \\ L_6 &= \{ w \mid \#b(w) = 1 \mathrel{\mathrm{mod}} 3 \} \\ \end{align} $$

A DFA can be constructed for $L_5$, because $L_5$ does not need infinite memory, so $L_5$ is regular. For $L_6$ the same reasoning as above. And for $L_4$ we can construct a DFA that simply does not accept $abc$, hence regular.

$L_1$ is regular because regular languages are closed under intersection.

For $L_2$ we can divide the language thus: $L_2 = L_5 \cap L_7$ where

$$ \begin{align} L_5 &= \{ w \mid \#a(w) \text{ is even} \} \\ L_7 &= \{ w \mid \#b(w) \lt \#c(w) \} \\ \end{align} $$

We now that a DFA can be constructed for $L_5$, hence $L_5$ is regular. $L_7$ is context-free because we can construct a PDA where the stack counts the number of $a$s and $b$s.

$L_2$ is hence context-free because the intersection of a regular language and a context-free language result in a context-free language.

For $L_3$ we can see that it's not context-free because where are limited to 1 stack.

Is my reasoning right?

Answer 1

Your reasoning for the positive statements seems sound to me, although they lack some detail if formal proofs are required. In particular, you might at least want to give the automata for $L_4,L_5,L_6$ and $L_7$; especially the latter can be considered non-trivial, depending on your level of expertise.

You lack proofs for

• $L_2 \notin \mathrm{REG}$ and
• $L_3 \notin \mathrm{CFL}$.

Both are true and straight-forward to prove; you find all you need in our reference questions for the regular and context-free case, respectively.