# Defining if a language is regular [duplicate]

$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.

## Edit

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?

## EDIT 2

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.

• "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. – Raphael Jul 19 '15 at 16:12

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$?)