I have just started learning Automata Theory, so far I only know about regular languages, FSM (NFAs and DFAs) and regular grammars, but I come across a question like this:

"Given the next languages, design their respective DFAs"

$L := \{a^nb^m |\ n>m\ ∧ n-m = odd\}$

$L := \{a^nb^m |\ n>m\ ∧ n-m = even\}$

$L := \{a^kb^mc^t |\ k \ \ is \ \ even \ \ ∧ \ \ m \ \ is \ \ odd \ \ ∧ \ \ t = 2m \ \}$

Is this even possible? because I was told these languages are regular...


Short answer - you're being lied to. From pumping lemma you can prove all three of these to not be regular languages.

Long answer - since you don't know it yet I don't know into how much detail I should go, but just for the sake of completeness I will give you the strings for given $p$ and the $n$ with which you would prove that the language does not have the pumping property.

For the first it would be for example $a^{p+1}b^{p}$. From this definition you know that because of $|xy|\le p$ and $|y|\ge 1$ you know that y will be $a^k$ where $k>0$. Then for $n=0$ you get $xy^0z = a^lb^{p}$ where $l<p+1 \implies l \le p$ which means this string is not from the first language $L$.

Similarly for the second language you can have $a^{p+2}b^p$. If $|y|\ge 2$ you can again chose $n = 0$ as in the last exercise. If $|y|=1$ you can chose $n = 2$ giving you string $a^{p+3}b^p$ which does not satisfy the condition $n-m=even$.

For the last I'd choose $a^0b^{2p+1}c^{4p+2}=b^{2p+1}c^{4p+2}$. Simiraly as in the first exercise you will alway only pump $b$ obviously violating $t=2m$ with any $n$ except for $1$.

| cite | improve this answer | |

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