What is the regular grammar of the language: $$L=\left\{a^nb^nc^md^m\left|n,m\ge 1\right|\right\}\:above\:\Sigma =\left\{a,\:b,\:c,\:d\right\}$$
My attempt: $$S\rightarrow aAbcBd|aXd$$ $$A\rightarrow aAb|\epsilon$$ $$B \rightarrow cBd|\epsilon$$
But I'm not sure if I'm right until here. Is it good?
Edit: This language is not regular, for this language you can look for the answer down: $$L=\left\{a^nb^nc^md^m\left|n,m\ge 1\right|\right\} \cup \left\{a^nb^mc^md^n\left|n,m\ge 1\right|\right\}$$
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ I don't understand what you intend $X$ for. And this grammar is not regular (indeed, no regular grammar exists for that language). $\endgroup$– riciCommented Mar 29, 2021 at 17:53
-
$\begingroup$ Just delete the second rule for $S$ and that's enough. $\endgroup$– NathanielCommented Mar 29, 2021 at 18:13
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Here's a simpler grammar: $$ S\rightarrow XY\\ X\rightarrow aXb\mid ab\\ Y\rightarrow cYd\mid cd $$ The key observation in cases like this is that strings in the language consist of two pieces concatenated: $a^nb^n$ and $c^md^m$, each of which can be generated by a simple grammar.
answered Mar 29, 2021 at 19:42