1
$\begingroup$

Decide whether the language $L$, defined by the following grammar is regular or not:
$S \rightarrow aab$
$S \rightarrow aacSb$
$S \rightarrow acSab$
$S \rightarrow acSacSb$

Where should I start?
I have tried defining a new language $L' = \{(aac)^n\ w\ b^n | w \in L\}$, which should be non-regular, because of dependency on $n$ with different left and right sides and since $L' = L$, $L$ has to be non-regular too, but I'm not sure whether this technique is valid.

$\endgroup$

1 Answer 1

1
$\begingroup$

The first step is to show that $$ L \cap (aac)^*aabb^* = \{ (aac)^n aab b^n : n \geq 0 \}. $$ Given that, you argue as follows: If $L$ were regular, then $L \cap (aac)^*aabb^*$ would also be regular. You can show in various ways that $\{ (aac)^n aab b^n : n \geq 0 \}$ isn't regular. It follows that $L$ isn't regular.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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