Consider the following NDFA Prove that each accepting string has the same number

Question

Consider the following NDFA Prove that each accepting string has the same number of 0 and 1 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 delta(q0, x) = q0 if and only if x is proper and contains the same number of 0 and 1 delta(q0, x) = q1 if and only if x is proper and contains one more 0 than 1 delta(q0, x) = q2 if and only if x is proper and contains one more 1 than 0 (d) delta(q0, x) = q3 if and only if x is not proper What strings are accepted by the NDFA?

Explanation / Answer

Non Deterministic Finite Automata: The following definition rephrases all basic definitions given for deterministic finite automata in the nondeterministic case. Definition A nondeterministic finite automata is a quintuple ; where: •Q is a finite set of states; •å is a finite set of input symbols; •d is the, possibly partial, transition function •d:A transition function that takes a state in Q and an input symbol in I as arguments and returns a subset of Q. • q0 element of Q is called the initial state; •F contained in Q is called the set of final states. The above definition states that a nondeterministic finite automaton can exhibit several different transition sequences for a given state and a given input. An input string is accepted by a nondeterministic finite automaton if and only if at least one of the possible transition sequences, defined by the input, leads to a final state. As language recognizer devices, nondeterministic automata are not more powerful than their deterministic counterpart, indeed they accept the same class of languages, that is to say they are equivalent. However, they are very often more convenient to use. In many cases, the most direct formalization of a problem is in terms of a nondeterministic automaton.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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