This question already has an answer here:

$L_4 = \{ w | w \text{ does not contain symbol a immediately followed by symbol b} \} $

where: $ \Sigma = \{ a, b, c \} $

So far I believe I have a defined regular grammar for this language, however I am having trouble coming up with an equivalent regular expression.

$<Language\_4> ::= a <AOrC> $

$<Language\_4> ::= b <Language\_4> $

$<Language\_4> ::= c <Language\_4> $

$<Language\_4> ::= \epsilon $

$<AOrC> ::= a <Language\_4> $

$<AOrC> ::= c <Language\_4> $

$<AOrC> ::= \epsilon $

Via a standard regex grammar this could be done via a lookahead, however I don't believe that the lookahead operation is a valid regular language operation. I'm having trouble proving that if it is true though.

This is for a homework assignment, so I'm not expecting a full answer just some pointers in the right direction.


I went through this set of answers: How to convert finite automata to regular expressions?

I then used Arden's Lemma as it seemed the most straight-forward.

First I defined:

$Q_0 = aQ_1 \cup bQ_0 \cup cQ_0 \cup \epsilon $

$Q_1 = cQ_0 \cup aQ_1 \cup \epsilon $

$ Q_1 = cQ_0 \cup aQ_1 \cup \epsilon $

Apply Arden's Lemma:

$ U = a $, $ L = Q_1 $, $ V = cQ_0 $

Then I get:

$Q_1 = a * c Q_0 \cup \epsilon $

By then substituting $Q_1$ into $Q_0$ I get:

$Q_0 = a[a*cQ_0 \cup \epsilon] \cup bQ_0 \cup cQ_0 \cup \epsilon $

$Q_0 = \underbrace{(aa * ac \cup b \cup c)}_U \underbrace{Q_0}_L \cup \underbrace{a \cup \epsilon }_V $

$Q_0 = (aa * ac \cup b \cup c)* a$

Is this a correct application of the lemma?


I've tested the regex more and it doesn't match the desired language. I think there may be an error in my application of the lemma. I'm going to try the application again in case I missed something.


marked as duplicate by D.W., David Richerby, Raphael Jul 19 '15 at 16:12

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ "Please comment my work-in-progress solution attempt" does not make for a good SE question. Do you have any specific questions about your attempts? Please clarify and highlight these. $\endgroup$ – Raphael Jul 19 '15 at 16:12

Hint: Here are a few easier languages to practice on:

  1. Every occurrence of the symbol $a$ is followed by a non-$a$ symbol. (Hint: every $a$ occurs in the context of $ab$ or $ac$.)

  2. No occurrence of the symbol $a$ is followed by another $a$. (The only difference from 1 is that a word could end with $a$.)

  3. Every occurrence of the symbol $a$ is followed by a non-$b$ symbol. (Hint: what are the possible contexts of $a$?)

  4. Your language. (Combine the answers to 3 and 2.)


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