What exactly is the difference between $$ C = \{a^*\}\{b\}\{a^*\}\{b\}\{a^*\}\{b\} $$ and $$ D = \{a^nba^nba^nb | n \geq 0 \} $$
It is known that D is non-regular and C is regular, but I am not sure why.
1
-
$\begingroup$ In $C$ you concatenate arbitrary choices of words from each of the factors. For example, $a^2ba^3ba^5b\in C$. You have that $D\subsetneq C$, but in the elements of $D$ the same choice $a^n$ that was used for the word from the first factor $\{a^*\}$ is used as the choice from the other two factors $\{a^*\}$. $\endgroup$– plopOct 5, 2020 at 18:24
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
The exact difference is that the expression for D uses -the same n- for all the 'a' substrings. The expression for C does not impose that restriction on its strings, i.e each of the 'a' substrings of a string in C may or may not be of different lengths.
$\begingroup$
$\endgroup$
C is a regular expression over $\Sigma\{a,b\}$. We can design a finite automaton that can accept the language which can be generated from C. On the other hand, the language D is not regular. Using pumping lemma for regular language it can be proved that D is not regular. Hope this will help you. If you need more explanation then please feel free to ask.
