Given a language determine if it is regular, context free, and/or decidable. No proof needed, but an explanation would be appreciated.
A = {a^n b^(2n+6) | n >= 0}
- My first guess is no its definitely not regular as it would require memory to compute.
- I don't think its context free because I think we can use the pumping lemma and pump a^n. But I'm not very sure on this. If it is context free, why?
- If its not regular and not context free, I don't really know how to tell if the language is decidable or not. Any help on this one would be really appreciated.
B = { (ab)^2n | n >= 0}
- I'm not sure on this one in any regard.
The first language is not regular. The proof is a straightforward application of the pumping Lemma.
It is, however, context free. Consider the grammar with symbol $S$ and production rules $S \gets b^6$, $S \gets aSbb$. Because it is context free, it’s also decidable.
The second language can be represented by the regular expression $(abab)^*$ and is therefore regular.