undefined | unit 2 nondeterminism and kleenes theorem

ALC

Unit 2Nondeterminism and Kleene’s Theorem Q1) What do you mean by minimal finite automata?Ans: Minimal finite automata If X and Y are two states in a DFA, we can combine these two states into {X, Y} if they are not distinguishable. Two states are distinguishable, if there is at least one string S, such that one of δ (X, S) and δ (Y, S) is accepting and another is not accepting. Hence, a DFA is minimal if and only if all the states are distinguishable. Algorithm Step 1: All the states Q are divided in two partitions: final states and non-final states and are denoted by P0. All the states in a partition are 0th equivalent. Take a counter k and initialize it with 0.Step 2: Increment k by 1. For each partition in Pk, divide the states in Pk into two partitions if they are k-distinguishable. Two states within this partition X and Y are k-distinguishable if there is an input S such that δ(X, S) and δ(Y, S) are (k-1)-distinguishable.Step 3: If Pk ≠ Pk-1, repeat Step 2, otherwise go to Step 4. Step 4: Combine kth equivalent sets and make them the new states of the reduced DFA.ExampleLet us consider the following DFA:

Figure example of DFALet us apply Algorithm 3 to the above DFA:

· P0 = {(c,d,e), (a,b,f)}

· P1 = {(c,d,e), (a,b),(f)}

· P2 = {(c,d,e), (a,b),(f)}

Hence, P1 = P2. There are three states in the reduced DFA. The reduced DFA is as follows:

Figure State Table and State Diagram of Reduced DFA Q2) What is the Kleene’s Theorem ?A2) Kleene’s TheoremKleen’s theorem states that an FA accepts any regular language and, conversely, that any language that an FA accepts is regular.Theorem 1: A finite automatic acknowledges every normal language.Proof: The general induction following the recursive description of regular language would prove this. Common step: The languages

, {

} and {a} for any symbol a in

are accepted by an FA.

Example:An NFA-

that accepts the language represented by the regular expression is given - (aa + b)*Sol: The given regular expression can be constructed using the operation, as below-

Q3) Write the Steps to Convert NFA with ε-move to DFA?A3) Steps to Convert NFA with ε-move to DFAStep 1: Take ∈ closure for the beginning state of NFA as beginning state of DFA.Step 2: Find the states that can be traversed from the present for each input symbol (union of transition value and their closures for each state of NFA present in current state of DFA).Step 3: If any new state is found take it as current state and repeat step 2.Step 4: Do repeat Step 2 and Step 3 until no new state present in DFA transition table.Step 5: Mark the states of DFA which contains final state of NFA as final states of DFA. Transition state table for DFA corresponding to above NFA

States	0	1
A, B, C	B, C	A, B, C
B, C	C	B, C
C	C	C

Fig: DFA State diagram

Q4) Define non - deterministic finite automata?A4) Non - deterministic finite automataIn NDFA, for a particular input symbol, the machine can move to any combination of the states in the machine. In other words, the exact state to which the machine moves cannot be determined. Hence, it is called Non-deterministic Automaton. As it has finite number of states, the machine is called Non-deterministic Finite Machine or Non-deterministic Finite Automaton. Q → Finite non-empty set of states.
∑ → Finite non-empty set of input symbols.
∂ → Transitional Function.
q0 → Beginning state.
F → Final State

● Review of a previous example of DFA

● Original version --- see Fig. (the same as Fig. 1.3.2)

Figure 1.4.1 Step 1 For NDFA ExampleA nondeterministic finite automaton (NFA) version of the above DFA --- see Fig. 2.6. ● More intuitive! ● How to design an NFA will be described later.

Figure 1.4.2 Step 1 For NDFA ExampleSome properties of NFA’s (see Fig. 2.6 for the illustration) --- Some transitions may “die,” like ˆ δ (q2, 0). Some transitions have multiple choices, like ˆ δ (q0, 0) = q0 and q2. Q5) What do you mean by equivalence of FA ?A5) Equivalence of FAIt would seem superficially that deterministic and non-deterministic finite state automata are totally distinct beasts. However, it turns out that they are equivalent. There is a DFA for every language recognized by an NFA that recognizes that language and vice versa. The NFA to DFA conversion algorithm is relatively simple, even though the resulting DFA is substantially more complicated than the original NFA. I will illustrate this equivalence after the hop and also go through a brief example of converting an NFA to an equivalent DFA. DFA and NFA Theorem proof -Let's formally state the theorem we are proving before continuing: Theorem:Let the language L ⊆ Σ* be recognized by NFA N = ( Σ , Q, q0, F, δ) and assume L. A DFA D= (Σ, Q ', q'0, F', δ ') exists that also accepts L. (L(N)= L(D)). We are able to prove by induction that D is equal to N by allowing each state in the DFA D to represent a set of states in the NFA N. Let's define the parameters of D: before we start proofing, ● Q’ is equal to the powerset of Q, Q’ = 2Q● q’0 = {q0}● F’ is the set of states in Q’ that contain any element of F, F’ = {q ∈ Q’|q ∩ F ≠ Ø}● δ’ is the transition function for D. δ’(q ,a ) = Up∈ q δ(p , a)for q ∈ Q’ and a ∈ ΣIt's worth more explaining, I think δ '. Note that in the set of states Q 'in D, each state is a set of states from Q in N itself. Determine the transition δ (p,a) for each state p in state q in Q 'of D (p is a single state from Q). The union of all δ(q, a) is δ(q,a) .Now we will demonstrate δ’(q0’ , x) =δ’(q0 , x) that for every x i.e L(D) = L (N) A6) Simulation of DFA and NFALet N = (QN , Σ, δN , qN0 , FN ) be a NFA. The equivalent DFA D1 is obtained from the so-called subset construction (also called “power construction”). We define D = (QD, Σ, δD, qD0 , FD),Where ● The alphabet of D is that of N. ● The states of D are sets of states of N: QD = P(QN )● The initial state qD0 of D is {qN0 }.● The final states of D are those sets that contain the final state of N: FD = {S ∈ P(QN )| S ∩ FN 6= ∅} ● The transition function of D arises from the transition function of N as follows: δD(S, a) = Uq∈S δN (q, a)That is, δD(S, a) is the set of all states of N that are reachable from some state q via a. Proposition. For every NFA N, there is a DFA D such that L(D) = L(N) Q7) How we represent NFA graphically?A7) Graphically representation of an NFADigraphs called state diagrams can represent an NFA. Under which: ● There are vertices describing the state. ● The transitions are indicated by an arc labelled with an input character. ● An arrow marks the initial state. ● The double circle signifies the final condition. Example:

Q = {q0, q1, q2}

∑ = {0, 1}

q0 = {q0}

F = {q2}

Sol: Transition diagram

Transition Table:

Present state	Next state for Input 0	Next state of Input 1
→q0	q0, q1	q1
q1	q2	q0
*q2	q2	q1, q2

In the diagram above, we can see that if the current state is q0, the next state at input 0 will be q0 or q1, and the next state at input 1 will be q1. When the current state is q1, the next state will be q2 on input 0 and the next state will be q0.0, on 1 input. If the current state is q2, the next state is q2 on 0 input, and the next state will be q1 or q2 on 1 input. Q8) The NFA has 'non-deterministic' in its name because of: A) The outcome is undetermined. B) Path selection is non-deterministic C) Non-deterministic is the condition to be transited next D) All of the above dataA8) correct answer is “B”. Explanation: Non-determinist or deterministic depends on the definite route specified or unknown for the transition from one state to another (multiple paths). Q9) Draw a non-deterministic finite automaton which, at the end of a string containing 0, 1, accepts 00 and 11, e.g. 01010100 but not 000111010.0. A9) If the input value enters the final state, design an NFA of the same string, then it is acceptable if it is not acceptable. A given string's NFA is as follows:

Q10) Design a NFA for the transition table as given below:

Present State	0	1
→q0	q0, q1	q0, q2
q1	q3	ε
q2	q2, q3	q3
→q3	q3	q3

A10) Transition diagram

Here,δ(q0, 0) = {q0, q1} δ(q0, 1) = {q0, q2} Then, δ(q1, 0) = {q3} Then, δ(q2, 0) = {q2, q3} δ(q2, 1) = {q3} Then, δ(q3, 0) = {q3} δ(q3, 1) = {q3}

Sign Up