New answers tagged

0

The language is context free. Here is a hint: as you have proved, it isn't regular. Therefore, when you try to construct a PDA for this language you will have to use the stack. Try to think how to count numbers using the stack, maybe start with a simpler language like $\{0^n1^m\mid n\ge m\}$. This is the main "crux" of your problem :)


2

Yes, since we can let $i$ be 0. Every non-empty word $x\in L$ can be expressed as "$xx^0\epsilon$". We can also let $i$ be 1. Every non-empty word $x\in L$ can be expressed as "$\epsilon x^1\epsilon$". The statements above are rather trivial and banal. So, the real question is, given a regular language $L$, is there some $i\geq 2$ such ...


Top 50 recent answers are included