NDFA accepting two consecutive a’s or two consecutive b's.

RGPV 2020
Construct a NDFA accepting all string in {a,b} with either two consecutive a’s or two consecutive b's.

Ans.

Read More

RGPV TOC Short note on equivalent of DFA and NFA

RGPV 2010, 02
Q. Write short note on equivalent of DFA and NDFA ?

Ans. 

1. Every DFA is an NDFA.
2. If from a regular set an NDFA is created than there may be chances of existence of DFA.

DFA is 5 tuple machine:

M = (Q, Σ, δ, q0, F)

1. Q is a finite non empty set of states.
2. Σ is a finite non empty set of input symbols.
3. δ is a transition function, QXΣ int to Q
4. q0 is an initial state belong to Q.
5. F is the set of final states belong to Q.

NDFA is 5 tuple machine:

M = ( Q, Σ, δ, q0, F )

1. Q is a finite non empty set of states.
2. Σ is a finite non empty set of input symbols.
3. δ is a transition function, QXΣ int to 2^Q 
4. q0 is an initial state belong to Q.
5. F is the set of final states belong to Q.

Problem 01: Convert the following Non-Deterministic Finite Automata (NDFA) to Deterministic Finite Automata (DFA).

Transition table for NDFA from above NDFA transition diagram

State	Input 0	Input 1
->q0	q0	q0, q1
q1	-	*q2
q2	-	-

Transition table for DFA from above NDFA transition table

State	Input a	Input b
->q0	q0	{q0, q1}
{q0, q1}	q0	*{q0, q1, q2}
*{q0, q1, q2}	q0	*{q0, q1, q2}

Transition diagram from above DFA transition table

Reference:

1. Introduction to Automata Theory Language & Computation, Hopcroft& Ullman,
2. Theory of Computation, Chandrasekhar & Mishra, PHI.

Read More

RGPV TOC What do you understand by DFA how to represent it

RGPV 2015,14,02,03
Q. What do you understand by DFA (Deterministic Finite Automata) and how is it represented ?

Ans. A DFA means Deterministic finite automata or a finite state automata or a deterministic finite state machine (DFSM) or deterministic finite acceptor (DFA).

It is a 5 tuple machine,

M = (Q, Σ, δ, q0, F)

1. Q is a finite non empty set of states.
2. Σ is a finite non empty set of input symbols.
3. δ is a transition function, QXΣ int to Q
4. q0 is an initial state belong to Q.
5. F is the set of final states belong to Q.

Lets take and example to under statnd DFA,

Construct a DFA for the language accepting strings starting with ‘01’ over input alphabets ∑ = {0, 1}.

Sol. Examples of strings accepted,

• 01
• 0101
• 01000000
• 01111111, etc

Here 01 consist 2 characters, so length is 2.

So minimum number of states required = 2+1 = 3.

Read More

DFA which accept 00 and 11 at the end of a string

Construct a NDFA and DFA accepting string having 00 and 11 at the end of the string with input (0,1).

Solution.

Read More