I'm trying to prove the language L = {$0^n 𝑥1^𝑛$ | x ∈ Σ*, n ≥ 1} is regular, but don't know how to present it in a DFA/NFA. I'm thinking to have n+1 states in a NFA, with the start state as the accepting state. The NFA reada $0$s to go from q$0$ to q$n+1$, then reading $1$s or $0$s to stay in the q$n+1$, then reading the same number of $1$s to go back to the q$0$. Is this a valid way to prove L is regular?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ There is no limit to $n$: the number of states of a finite automaton can't grow with it. (Oops - didn't see one star.) $\endgroup$– greybeardCommented Oct 4, 2020 at 7:42
-
$\begingroup$ Showing an FA with that language might convince even me that $L$ was regular. $\endgroup$– greybeardCommented Oct 4, 2020 at 8:03
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
Your language consists of all words starting with $0$ and ending with $1$.
answered Oct 4, 2020 at 8:04
$\begingroup$
$\endgroup$
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, but this is a trick question. See the answer by Yuval.
answered Oct 4, 2020 at 14:14
$\begingroup$
$\endgroup$
Your language is regular and can be rewritten as $$ L = {0\Sigma^*1}
$$ (start with 0 end with 1)
