# Tag Info

2

Yes, here the idea of one with three states. I don't know stuff formally enough to write tuples. Keep track of the parity of 'a's you read in two states. If you read 'aa', push A on the stack When you hit b, you better be on odd parity Pop 'A' for every 'b' you read At the end of the input, succeed if the stack is exactly empty. This accepts only when i == ...

1

Your language is regular and can be rewritten as $$L = {0\Sigma^*1}$$ (start with 0 end with 1)

2

Your solution depends on $n$. In this case the $n$ in the formulation of the language is not a constant, but a variable ranging over the positive integers $n\ge 1$. So we need strings of the form $0^n x 1^n$ for any $n\ge 1$, and any $x\in\Sigma^*$. In general that would not be possible with a FSA, it cannot count and compare the numbers of $0$'s and $1$'s, ...

4

Your language consists of all words starting with $0$ and ending with $1$.

Top 50 recent answers are included