In all the answers always explain their correctness . Question 1: Consider the f

Question

In all the answers always explain their correctness

. Question 1: Consider the following NDFA 0 1. Prove that each accepting string has the same number of 0 and 1 2. We say that a string r is proper if each prefix of r 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) (40,x) = if and only if x is proper and contains the same nurnber of 0 and (b) (go,z) = q1 if and only if is proper and contains one more 0 than 1 (c) ( ,x) = g2 if and only if x is proper and contains one more 1 than 0 (d) (go,x) = 93 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 qs 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 i1. After i +1 letters of course you can switch state. For example you may be in qi 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

Part (1) From the given NDFA, it is clear that:

We reach to states q1 and q2 by reading 0 and 1 respectively. Further, to reach back to an accepting state q0 from q1 and q2 we will needing a parallel reading of 1 and 0 respectively. This means that every read 0 that takes q0 to q1 must be followed by a 1 to come back to an accepting state, similarly for the q2. Hence, landing on an accepting state requires equal occurences of 0 and 1 read. Which in other words means, each accepting string must have and equal 0's and 1's. (NOTE: as after reaching to q3 from q1 and q2, there is no transaction that can revert the states back to q1 and q2, hence q3 is effectively a dead state and must be discarded for considering the set of accepting strings)

2) To understand this let us look at the following observations:

This means, that if x is an accepting string, which has equal count for 0 and 1, and we partion its prefix at any postion, it will at maximum separate one 0 and 1 leaving either one 0 more than 1 or one 1 more than 0.

This will be better clear by the opposite logic. Let us consider the case where, x is not proper that means, a prefix of x has the difference of more than one in either 0 or 1. For example: 11. 11 has 11 as its prefix which has 2 more 1's than the 0's present and it can only happen when 0's and 1's did not happen in pair, which is the case with state q3 only.

Now, with above understanding, to apply induction we can start with the string of length one i.e. 0 or 1 or empty string.

For example:

for part (a) to reach from q0 to q0 we will be needing the smalles string of empty string as our base case which will justify the claim because it has zero 1's as well as 0's in it.

for part (b) if by reading x we reach to q1, it means we have read one more 0 that 1's read so far. Take the base case of string 0. Which has zero 1's and one 0's which proves the proper-ness of x

for part (c) if by reading x we reach to q2, it means we have read one more 1 that 0's read so far. Take the base case of string 1. Which has zero 0's and one 1's which proves the proper-ness of x

for part (d) if we reach to state q3 from q0 after reading x, it measn either we have read 2 cosnecutive 1's or 0's, which makes the x not-proper (this we have discussed above, take the base case of 11 or 00)

Further to apply induction from here, combination of 0's and 1's for greater string sizes can be similarly formulated as base case, which will justify the results concurrently as already explained in the earlier mentioned 'observations'.

3) One transaction from q0 to q1 and then back to q0 adds a string '01' to the current read string, while going from q0 to q2 and coming bck to q0 adds '10' to the current state. Hence, it is easy to visualize that (as q3 is a dead state) any accepting string must formed by comobination of 01 and 10. This gives:

strings accepted by NDFA as: ( (01)* , (10)* )*

In words: 0 or more combintions of the 0 or more combinations of the 01 and 10.

Hope this helps! If you like the answer, please thumbs up!

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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