Consider the following NDFA: 1. Prove that each accepting string has the same nu

Question

Consider the following NDFA:

1. Prove that each accepting string has the same number of 0 and 1

2. We say that a string x is proper if each prefix of x has at most one more 0 than 1 and at most one more 1 than 0. Show by induction on the length of the string that the following 4 conditions hold (a) ?(q0, x) = q0 if and only if x is proper and contains the same number of 0 and 1

(b) ?(q0, x) = q1 if and only if x is proper and contains one more 0 than 1

(c) ?(q0, x) = q2 if and only if x is proper and contains one more 1 than 0

(d) ?(q0, x) = q3 if and only if x is not proper

Explanation: The base of the induction are string of size 1 and then you show directly that all the above properties hold (for example q3 can not be involved in strings of length 1). Show that if all 4 properties hold for all strings of size i they hold for all strings of size i + 1. After i + 1 letters of course you can switch state. For example you may be in q1 after i characters and a 0 comes and then you move to q3. Use in this case the induction hypothesis and the fact that the next char is 0 to prove the inductive assumption over q3.

3. What strings are accepted by the NDFA?

Explanation / Answer

The NDFA has a only one end state i.e. q0 which also happens to be the start state

q0 can be reached from q1 and q2 , there is no way to reach to q0 from q3.

q3 can only move to q3 on any input ( 1, 0 )

Below are the two accepting state movement :

a) q0 -> q1 -> q0

b) q0 -> q2 -> q0

Now the movement a) q0 -> q1 -> q0   happens on accepting 01 or any number of (01) pair or simply put it as (01)*

movement b) q0 -> q2 -> q0 happens on accepting 10 or any number of (10) pair or simply put as (10)*

Since both the accepting states have a 10 or 01 appear in pair for the string to be accepted by the NDFA. the number of 1's and 0's are always equal

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.