Question

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... ?

Was it helpful?

Solution

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.

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top