RGPV Define Mealy and Moore Machine

RGPV 2010
Q. Formally define the following (with example)-

1. Mealy machine

1. Moore machine

1. Mealy machine: Mealy machine is a six tuple machine.

M = (Q, Σ, △, δ, λ, q0)

1. Q is finite set of states.
2. Σ is the input alphabet.
3. △ is the output alphabet.
4. δ is transition function which maps Q×∑ → Q.
5. ‘λ’ is the output function which maps Q×∑→ △.
6. q0 is the initial state.

Transition table for Mealy machine

Present state	Next state
	a = 0		a = 1
	State	Output	State	Output
->q1	q1	0	q2	0
q2	q1	0	q2	1

Transition diagram for Mealy machine

1. Moore machine: Moore machine is a six tuple machine.

M = (Q, Σ, △, δ, λ, q0)

1. Q is finite set of states.
2. Σ is the input alphabet.
3. △ is the output alphabet.
4. δ is transition function which maps Q×∑ → Q.
5. ‘λ’ is the output function which maps Q → △.
6. q0 is the initial state.

Transition table for Moore machine

Present state	Next state		Output
	a = 0	a = 1
->q1	q1	q2	0
q2	q1	q3	0
q3	q1	q3	1

Transition diagram for Moore machine

Mealy machine vs Moore machine

Mealy machine	Moore machine
Output depends on present state as well as present input.	Output depends on the present state.
If input changes, output also changes	If input changes, output does not changes.
Compare to Moore less number of states are required. Because states do not depends on output.	Compare to Mealy more number of states are required. Because states depends on number of output.
Difficult to develop. Difficulty due to input affects output.	Easy to develop.
Output is placed on transition arrow.	Output is placed with state.

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 notes Write short note on NDFA

RGPV 2002
Q. Write a short note on non-deterministic finite automta ?

Ans. Non deterministic finite automata refere as NDFA or NFA allows a set of possible moves. 

For example from a state an input '1' can transit 0 times, 1 times or more than 1 times.

Its not determined in NFA like in DFA.

NDFA is defined as 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.

To understood NDFA, lets compare it with DFA.

NDFA	DFA
Non Deterministic Finite Automata	Deterministic Finite Automata
Empty String transition allowed in DDFA.	Empty String transition not allowed in DFA.
In NDDFA, the next possible state is not determined.	In DFA, the next possible state is determined.
For NDFA, DFA may or may not exist.	For all DFA there exist NDFA
NDFA is like combination of many machines.	DFA is like a single machine.
NDFA is easy to construct.	DFA is touch to construct compare to NDFA.

Some examples of NDFA:

Problem 01: Construct a NDFA for the language accepting strings having even number of 1's over input alphabets ∑ = {0, 1}.

Problem 02: Construct a NDFA for the language accepting strings containg '01' as substring over input alphabets ∑ = {0, 1}.

Problem 03: Construct a NDFA for the language accepting strings containg '0' as divisible by 3 over input alphabets ∑ = {0, 1}.

Read More