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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.