1
$\begingroup$

How to check if

$L = \{c^ka^nb^n \mid k>0 \wedge n\geqslant0\} \cup \{a, b\}^*$

is regular ,where

$L_1 = \{c^ka^nb^n \mid k > 0 \wedge n\geqslant0\}$ is clearly not regular and $L_2 = \{a, b\}^*$ is... ?

$\endgroup$
5
  • $\begingroup$ Closure under union $\endgroup$ – VimForLife May 2 '20 at 8:21
  • $\begingroup$ so when L1 is not regular, and L is the union of L1 and L2 , automaticly L isn't regular ? $\endgroup$ – Stukata May 2 '20 at 8:24
  • $\begingroup$ Correct! You cannot build (e.g. DFA) the union of a regular and non-regular language. $\endgroup$ – VimForLife May 2 '20 at 8:28
  • 2
    $\begingroup$ Wrong. For example, $\{a^nb^n \mid n \geq 0\} \cup a^*b^*$ is regular. $\endgroup$ – Yuval Filmus May 2 '20 at 9:18
  • $\begingroup$ Look for a sub-language easy to prove non-regular. $\endgroup$ – greybeard May 2 '20 at 18:32
1
$\begingroup$

If $L$ were regular than so would the following language be: $$L \cap ca^*b^* = \{ ca^nb^n \mid n \geq 0 \}.$$ You can show that the latter language is not regular in various ways.

$\endgroup$
1
  • $\begingroup$ Thank you for editing the post, ill learn to use the website so i can make better posts! And thanks for the suggestion! $\endgroup$ – Stukata May 2 '20 at 11:22

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.