EasyExamNotes.com: RGPV TOC PYQ

Showing posts with label RGPV TOC PYQ. Show all posts

CNF from S-->aAD;A->aB/bAB;B->b,D->d.

Jayesh Umre 11/22/2020 cfg to cnf, RGPV TOC PYQ, TOC No comments

RGPV 2020
Find the grammar in Chomsky Normal form equivalent to S-->aAD;A->aB/bAB;B->b,D->d.

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

Jayesh Umre 11/22/2020 dfa nfa example, RGPV TOC PYQ, TOC No comments

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

Ans.

Regular expresion to CFG

Jayesh Umre 11/22/2020 cfg, Regular Expression, RGPV TOC PYQ, TOC No comments

RGPV 2020
Write given CFG for R.E (011 + 1)(01).

Regular expression to Regular grammar

Jayesh Umre 11/22/2020 Regular Expression, RGPV TOC PYQ, TOC No comments

RGPV 2020
How can we construct regular grammar from regular expression?

Grammar is ambiguous. S → aSbS|bSaS|∈

Jayesh Umre 11/22/2020 RGPV TOC PYQ, TOC No comments

RGPV 2020
Show that the following grammar is ambiguous.
S → aSbS|bSaS|∈

Ans. For grammar to be ambiguous, there should be more than one parse tree for same string.

Above grammar can be written as

S → aSbS

S → bSaS

S → ∈

Lets generate a string 'abab'.

So, now parse tree for 'abab'.

Left most derivative parse tree 01

S → aSbS

S → a∈bS

S → a∈baSbS

S → a∈ba∈b∈

S → abab

Parse Tree 01

Left most derivative parse tree 02

S → aSbS

S → abSaSbS

S → ab∈aSbS

S → ab∈a∈bS

S → ab∈a∈b∈

S → abab

Parse tree 02

So there are more than 1 parse tree for same string, that means grammar is ambiguous.

leftmost and rightmost derivations

Jayesh Umre 11/22/2020 Parse tree, RGPV TOC PYQ, TOC No comments

RGPV 2020
What are leftmost and rightmost derivations? Explain with suitable example ?

Construct Moore machine for Mealy machine

Jayesh Umre 11/22/2020 Mealy Moore, Moore to Mealy, RGPV TOC PYQ, TOC No comments

RGPV 2020
Construct Moore machine for the following Mealy machine.

Sol.

Transition table for above Mealy machine.

Present State	Next State
	Input = 0		Input = 1
	State	Output	State	Output
q0	q0	0	q1	1
q1	q2	2	q0	0
q2	q1	1	q2	2

Transition table for Moore machine from above Mealy machine transition table.

Present State	Next State		Output
Present State	Input = 0	Input = 1	Output
q0	q0	q1	0
q1	q2	q0	1
q2	q1	q2	2

Transition diagram for Moore machine fram above Moore machine transition table.

CFL are not closed under intersection

Jayesh Umre 11/22/2020 RGPV TOC PYQ, TOC No comments

RGPV 2020

Preve that CFL are not closed under intersection ?

DFA end with 1 contain 00 | RGPV TOC draw

Jayesh Umre 10/10/2020 RGPV TOC PYQ 1 comment

RGPV 2007
Q. Define deterministic finite automta. Draw DFA that accepts any string which ends with 1 or it ends with an even number of 0's following the last 1. Alphabets are {0,1}.

Ans. Some example strings = {1, 001, 01001, 011}

NFA to DFA | RGPV TOC

Jayesh Umre 10/10/2020 RGPV NFA to DFA, RGPV TOC PYQ, RGPV TOC Unit 2, TOC No comments

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
State	a	B
è q0	q0, q1	q0
q1	q2	q1
q2	q3	q3
q3	-	q2

Transition table for DFA from given NFA table

State	Input
State	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

Moore to Mealy | RGPV TOC PYQ

Jayesh Umre 10/10/2020 Moore to Mealy, RGPV TOC PYQ, RGPV TOC Unit 2, TOC No comments

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

Present State	Next State		Output
Present State	a = 0	a = 1	Output
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

DFA accept even 0 and even 1 |RGPV TOC PYQ

Jayesh Umre 10/10/2020 Draw DFA, RGPV TOC PYQ, RGPV TOC Unit 2, TOC No comments

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}

Short note on automata | RGPV TOC PYQ

Jayesh Umre 10/10/2020 RGPV TOC PYQ, TOC No comments

RGPV 2010
Q. Write short note on automata ?

Ans. An automaton is an abstract model of a digital computer.

Some types of automata :

Finite-state machine.
Pushdown automata.
Turing machine

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

Jayesh Umre 10/10/2020 Draw DFA, RGPV TOC PYQ, RGPV TOC Unit 2, TOC No comments

RGPV 2015
Q. Design DFA accepting the following languages over the alphabet {0, 1}
The set of all words ending in 00.
The set of all words except ε.
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)*

DFA ending with 101 | RGPV TOC PYQ

Jayesh Umre 10/09/2020 Draw DFA, RGPV TOC PYQ, RGPV TOC Unit 2, TOC No comments

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

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

Jayesh Umre 10/09/2020 Draw DFA, RGPV TOC PYQ, RGPV TOC Unit 2, TOC No comments

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

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

Minimum number of states required = 2.

Construct FA divisible by 3 | RGPV TOC PYQ

Jayesh Umre 10/09/2020 Draw DFA, RGPV TOC PYQ, RGPV TOC Unit 2, TOC No comments

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

Construct DFA equivalent to NFA | RGPV TOC PYQ

Jayesh Umre 10/09/2020 RGPV NFA to DFA, RGPV TOC PYQ, TOC No comments

RGPV 2014
Q. Construct DFA equivalent to the NFA
M = ({p, q, r, s}, {0, 1}, δ, p, {q, s})
Where δ is defined in the following table.
δ
0
1
p
{q, s}
{q}
q
{r}
{q, r}
r
{s}
{p}
s
-
{p}

Ans.

State	0	1
[p]	[q, s]	[q]
[q]	[r]	[q, r]
[q, s]	[r]	[q, r, p]
[r]	[s]	[p]
[q, r]	[r, s]	[q, r, p]
[q, r, p]	[q, s, r]	[p, q, r]
[s]	Φ	[p]
[r, s]	[s]	[p]
[q, s, r]	[r, s]	[p, q, r]

RGPV TOC design finite automata problems

Jayesh Umre 10/08/2020 RGPV TOC PYQ No comments

RGPV 2008
Prob 01: Designa FA which accepts set of strings containing four 1's in every string over alphabet ∑ = {0, 1}.

Ans. Some example strings = {1111,0110101, 001100110}

RGPV 2016
Prob 02. Design NFA that accepts all strings with at most 3 a's.

Ans. Some example strings = {aaa, baba, a, ab}

RGPV 2014
Prob 03: Construct a finite automata for the language {0ⁿ | n mod 3 = 2, n>=0}

Ans. Some example strings = {00,00000,00000000}

RGPV 2016
Design a NFA for {cbabⁿ | n>=0}

Ans. Some example strings = {cba, cbab, cbabb, cbabbb}

RGPV 2020 Find the grammar in Chomsky Normal form equivalent to S-->aAD;A->aB/bAB;B->b,D->d.

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

RGPV 2020 Write given CFG for R.E (011 + 1)*(01)*.

RGPV 2020 How can we construct regular grammar from regular expression?

RGPV 2020Show that the following grammar is ambiguous. S → aSbS|bSaS|∈

Left most derivative parse tree 01

Left most derivative parse tree 02

RGPV 2020 What are leftmost and rightmost derivations? Explain with suitable example ?

RGPV 2020Construct Moore machine for the following Mealy machine.

RGPV 2020

Preve that CFL are not closed under intersection ?

RGPV 2007Q. Define deterministic finite automta. Draw DFA that accepts any string which ends with 1 or it ends with an even number of 0's following the last 1. Alphabets are {0,1}.

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

Convert the following NFA into DFA.

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

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

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

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

RGPV 2010Q. Write short note on automata ?

RGPV 2015Q. Design DFA accepting the following languages over the alphabet {0, 1}The set of all words ending in 00.The set of all words except ε.The set of all words that begin with 0.

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

RGPV 2009Q. Construct DFA for anb | n>=0.

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

RGPV 2009construct DFA for binary integer divisible by 3

RGPV 2014Q. Construct DFA equivalent to the NFAM = ({p, q, r, s}, {0, 1}, δ, p, {q, s})Where δ is defined in the following table.δ 01p{q, s}{q}q{r}{q, r}r{s}{p}s-{p}

RGPV 2008Prob 01: Designa FA which accepts set of strings containing four 1's in every string over alphabet ∑ = {0, 1}.

RGPV 2016Prob 02. Design NFA that accepts all strings with at most 3 a's.

RGPV 2014 Prob 03: Construct a finite automata for the language {0n | n mod 3 = 2, n>=0}

RGPV 2016Design a NFA for {cbabn | n>=0}

More subjects to read

jku

RGPV 2020
Find the grammar in Chomsky Normal form equivalent to S-->aAD;A->aB/bAB;B->b,D->d.

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

RGPV 2020
Write given CFG for R.E (011 + 1)(01).

RGPV 2020
How can we construct regular grammar from regular expression?

RGPV 2020
Show that the following grammar is ambiguous.
S → aSbS|bSaS|∈

RGPV 2020
What are leftmost and rightmost derivations? Explain with suitable example ?

RGPV 2020
Construct Moore machine for the following Mealy machine.

RGPV 2007
Q. Define deterministic finite automta. Draw DFA that accepts any string which ends with 1 or it ends with an even number of 0's following the last 1. Alphabets are {0,1}.

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

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

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}.

RGPV 2010
Q. Write short note on automata ?

RGPV 2015
Q. Design DFA accepting the following languages over the alphabet {0, 1}
The set of all words ending in 00.
The set of all words except ε.
The set of all words that begin with 0.

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

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

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

RGPV 2014
Q. Construct DFA equivalent to the NFA
M = ({p, q, r, s}, {0, 1}, δ, p, {q, s})
Where δ is defined in the following table.
δ
0
1
p
{q, s}
{q}
q
{r}
{q, r}
r
{s}
{p}
s
-
{p}

RGPV 2008
Prob 01: Designa FA which accepts set of strings containing four 1's in every string over alphabet ∑ = {0, 1}.

RGPV 2016
Prob 02. Design NFA that accepts all strings with at most 3 a's.

RGPV 2014
Prob 03: Construct a finite automata for the language {0ⁿ | n mod 3 = 2, n>=0}

RGPV 2016
Design a NFA for {cbabⁿ | n>=0}