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?

  • 1
    $\begingroup$ Your reasoning seems to lack arguments about why #b(w) < #c(w) is not regular and why #a(w) < #b(w) < #c(w) is not context free. Pumping lemma should be good for both. $\endgroup$ – Karolis Juodelė Jan 3 '13 at 16:33
  • $\begingroup$ Hi ! This is all questions from an exam and in the question it's stated that a brief, informal explanation is sufficient. Therefore using the pumping lemma is not needed. $\endgroup$ – mrjasmin Jan 3 '13 at 16:38
  • 2
    $\begingroup$ In that case the only thing I disagree with is your DFA "that simply does not accept 'abc'" it might be that your thinking is correct but the way it is worded I get the feeling you mean that the DFA accepts $\Sigma^{*} - abc$ which isn't enough. $\endgroup$ – Sam Jones Jan 3 '13 at 21:02
  • $\begingroup$ Your soluton to (3) isn't clear enough. You'd have to argue no PDA can do what is asked here, "need two stacks" exactly why? $\endgroup$ – vonbrand Feb 11 '13 at 11:02

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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