0
$\begingroup$

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.

$\endgroup$
  • $\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$ – plop Oct 5 '20 at 18:24
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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