NFA to DFA | RGPV TOC

RGPV 2009
Q. Construct minimized DFA for the given NFA.
Or

Convert the following NFA into DFA.

Ans.

Transition table for given NFA

State	Input
	a	B
è q0	q0, q1	q0
q1	q2	q1
q2	q3	q3
q3	-	q2

Transition table for DFA from given NFA table

State	Input
	a	B
è [q0]	[q0, q1]	[q0]
[q0, q1]	[q0, q1, q2]	[q0, q1]
[q0, q1, q2]	[q0, q1, q2, q3]	[q0, q1, q2]
[q0, q1, q2, q3]	[q0, q1, q2, q3]	[q0, q1, q2, q3]
[q0, q1, q2]	[q0, q1, q2]	[q0, q1, q2]

Transition diagram for DFA from above DFA transition table

Read More

Moore to Mealy | RGPV TOC PYQ

RGPV 2009
Construct a Mealy mcahine which is equivalent to the Moore mchine given below.

Present State	Next State		Output
	a = 0	a = 1
q0	q1	q2	1
q1	q3	q2	0
q2	q2	q1	1
q3	q0	q3	1

Ans. Mealy machine

Present State	Next State
	a = 0		a = 1
	Next State	Output	Next State	Output
q0	q1	0	q2	1
q1	q3	1	q2	1
q2	q2	1	q1	0
q3	q0	1	q3	1

Mealy machine

Read More

DFA accept even 0 and even 1 |RGPV TOC PYQ

RGPV 2011
Design FA which accepts even no. of 0's and even no. of 1's.
Or

RGPV 2010
Construct DFA ove input alphabet Σ = {0,1} to accept string which contains no. of 0 is even and no. of 1 is even.
Or

RGPV 2008
Construct DFA accepting set of all strings containing even no. of a's and even no. of b's over input alphabet {a,b}.

Ans. Some example strings = {00, 11, 0011, 0101, 0110}

Read More

DFA ending with 00 start with 0 no epsilon | RGPV TOC PYQ

RGPV 2015
Q. Design DFA accepting the following languages over the alphabet {0, 1}

1. The set of all words ending in 00.

1. The set of all words except ε.

1. The set of all words that begin with 0.

Ans. 

1. The set of all words ending with 00:

Some example strings = {00, 100, 000, 1000,0100,11100}

Regular expression = (0+1)*00

2. The set of all words except ε:

Some example strings = {0, 1, 00, 10, 01, 11, 000000, 11111}

Regular expression = (0+1)(0+1)*

3. The set of all words that begin with 0:

Some example strings = {0, 01, 00000, 0101010101}

Regular expression = 0(0+1)*

Read More

DFA ending with 101 | RGPV TOC PYQ

RGPV 2006
Q. Give DFA accepting the language over alphabet {0,1} such that all strings of 0 and 1 ending in 101.

Ans. Some example strings = {101, 10101, 01101, 00101, 111o1, 1101}

Regular expression = (0+1)*101

Minimum number of states required = 4

Read More

Construct DFA for a power n, n>=0 || RGPV TOC

RGPV 2009
Q. Construct DFA for aⁿb | n>=0.

Ans. Some example strings = {ab, aab, aaab, aaaab}

Minimum number of states required = 2.

 

Read More

Construct FA divisible by 3 | RGPV TOC PYQ

RGPV 2010
Construct a finite automta that will accept those strings of a binary number that are divisible ny three.
or

RGPV 2009
construct DFA for binary integer divisible by 3

Ans. Some example strings = {0, 11, 110, 1001, 1100}

Minimum number of states required = 4

Read More