New answers tagged

11

If $n$ is fixed then $a^n$ is just a single word and so is $a^nb^n$. If by $a^n$ you mean the language $\{a^n \mid n \ge 0\}$ (whose corresponding regular expression is $a^*$) then the problem is that the variable $n$ in $a^n$ is independent of the variable with the same name in $b^n$. The language obtained by concatenating $A=\{a^n \mid n \ge 0\}$ with $B=\...


1

The automaton is deterministic, so any string over $\{0,1\}$ has a unique path. We need at least one $1$ to move from $q_1$ to the component where is the accepting state. Immediately after reading $1$ we are always in accepting state $q_2$. Look at the last $1$ in the input. At that moment we accept in $q_2$. To return to the accepting state, only reading $0$...


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