Cheap and Secure Web Hosting Provider : See Now

[Solved]: Finite Automata -- Determine if a set is regular

, , No Comments
Problem Detail: 

I have been at this for hours. The question is:

Prove that the language $A = \{0^kx \mid k > 0, x \in \{0,1\}^*, \text{ and } \#(0,x) \geq k\}$ is regular,

where $\#(n, x)$ denotes the number of $n$ in string $x$.

So far, I have used the pumping lemma to determine that the opposite is not regular, i.e. that if $\#(0,x) \leq k$, the language is not regular.

I have also constructed a nondeterministic finite automaton that I thought I could use to prove that this set is regular since that is generally the way to go about proving regularity. I can't really draw it, but at start state $s$, if $0$ is read in, then move to state 1 (or state $'0'$). If a $0$ is read in, either stay in state 1 or move to state 2. If a $1$ is read in, move to state 2. However, I honestly don't know what to do further.

Asked By : tdark

Answered By : Yuval Filmus

Hint: Show that a word belongs to $A$ iff it starts at $0$ and contains at least one more $0$. That is, $A$ is accepted by the regular expression $01^*0(0+1)^*$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35129

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback