[go: up one dir, main page]

0% found this document useful (0 votes)
304 views11 pages

Paper Automata

pvq of automata

Uploaded by

sapanghai297
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
304 views11 pages

Paper Automata

pvq of automata

Uploaded by

sapanghai297
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 11

lOMoARcPSD|21665779

KCS402-Theory of Automata and Formal Languages-aktutor

B.tech (Dr. A.P.J. Abdul Kalam Technical University)

Studocu is not sponsored or endorsed by any college or university


Downloaded by IT33_075_SAPAN GHAI (sapanghai297@gmail.com)
lOMoARcPSD|21665779

Printed Pages : 3 Roll No. NCS402

B.TECH.
THEORY EXAMINATION (SEM–IV) 2016-17
THEORY OF AUTOMATA AND FORMAL LANGUAGES

Time : 3 Hours Max. Marks : 100


Note : Be precise in your answer. In case of numerical problem assume data wherever not provided.

SECTION – A
1. Explain the following: 10 x 2 = 20
(a) Design the DFA that accepts an even number of a’s and even number of b’s.
(b) Consider the DFA given below and identify the L accepted by the machine.

(c) State the pumping lemma theorem for regular languages.


(d) Convert the FA given below to left linear grammar.

(e) Check whether the grammar is ambiguous or not.


R-> R+R/ RR/ R*/ a / b / c. Obtain the string w = a+b*c
(f) S->aB/bA A->a/aS/bAA B-> b/bS/aBB. Identify the strings obtained from this
grammar.
(g) Define PDA. Draw the graphical representation for PDA.
(h) Design a PDA which accepts set of balanced paranthesis ( { { } } ).
(i) Eliminate unit productions in the grammar. S->A/bb A->B/b B->S/a
(j) What are checking off symbols?

SECTION – B
2. Attempt any five of the following questions: 5 x 10 = 50
(a) (i) Convert the NFA- ε to DFA.

WWW.AKTutor.in
Downloaded by IT33_075_SAPAN GHAI (sapanghai297@gmail.com)
lOMoARcPSD|21665779

(ii) Check with the comparison method for testing equivalence of two FA given
below.

(b) Prove that the compliment, homomorphism and inverse homomorphism, closure of a
regular language is regular.
(c) State and prove kleene’s theorem with an example.
(d) Consider the grammar with the production S->aSS A->b. Compute the string aababbb
with the left most and right most derivation. Draw the derivation tree.
(e) (i) Find out whether the language L = {xnynzn | n ≥ 1} is context free or not.
(ii) Construct a PDA that accepts L = { wwR | w = (a+b)* }
(f) (i) Convert the following CFG into CNF
S → XY | Xn | p
X → mX | m
Y → Xn | o
(ii) Convert the following CFG into CNF S → ASA | aB, A → B | S, B → b | ε
(g) Design a TM to recognize all strings consisting of an odd number of α’s.
(h) Prove that the halting problem is undecidable.

SECTION – C
Attempt any two of the following questions: 2 x 15 = 30
3. (a) Minimize the automata given below

WWW.AKTutor.in
Downloaded by IT33_075_SAPAN GHAI (sapanghai297@gmail.com)
lOMoARcPSD|21665779

(b) Compute the epsilon- closure for the given NFA. Convert it into DFA.

4. (a) Construct PDA to accept L= {0n 1n | n > 0}


(b) Construct a PDA from the following CFG.
G = ({S, X}, {a, b}, P, S) where the productions are −
S → XS | ε , A → aXb | Ab | ab

5. (a) Prove that single tape machines can simulate multi tape machines.
(b) Design a TM to recognize all strings consisting of an odd number of α’s.

WWW.AKTutor.in
Downloaded by IT33_075_SAPAN GHAI (sapanghai297@gmail.com)
lOMoARcPSD|21665779

Printed Pages: 03 Sub Code: RCS403


Paper Id: 110433 Roll No.

B. TECH
(SEM IV) THEORY EXAMINATION 2017-18
THEORY OF AUTOMATA AND FORMAL LANGUAGES
Time: 3 Hours Total Marks: 70
Note: Attempt all Sections. If require any missing data; then choose suitably.

SECTION A

1. Attempt all questions in brief. 2 x 7 = 14


a. Define alphabet, string and language.
b. Design a regular expression that accepts all the strings for input alphabet {a,b}
containing exactly 2 a’s.
c. Design a NFA that accepts all the strings for input alphabet {a,b} containing
the substring abba.
d. Define Chomsky hierarchy.
e. Is context free language closed under union? If yes, give an example.
f. Convert NFA into equivalent DFA by taking any suitable example.
g. Remove useless productions from the given productions: SAB|ab,
AaA|B|a, BD|E

SECTION B

2. Attempt any three of the following: 7 x 3 = 21


a. Define Deterministic Finite Automata (DFA) and design a DFA that accepts
the binary number whose equivalent is divisible by 5.
b. State recursive definition of regular expression and construct a
regularexpression corresponding to the state transition diagram as shown in
Fig.1

Fig.1
c. Reduce the given grammar G=({S,A,B},{a,b},P,S) to Chomsky Normal Form.
Where P is defined as:
S→ bA | aB
A→ bAA | aS | a
B → aBB | bS | b
d. What is Push Down Automata (PDA)? Design the PDA for the language
L = {wcwR│w{a,b}*}
e. Define Turing Machine (TM). Construct the TM for the language
L = {anbn│n>0}.

WWW.AKTutor.in
Downloaded by IT33_075_SAPAN GHAI (sapanghai297@gmail.com)
lOMoARcPSD|21665779

SECTION C
3. Attempt any one part of the following: 7x1=7
(a) Describe Mealy and Moore machines with example. Convert the given Mealy
machine as shown in Fig. 2 into Moore Machine.

Fig. 2
(b) Construct the minimum state automata equivalent to DFA described by Fig. 3

Fig. 3
4. Attempt any one part of the following: 7x1=7
p
(a) State Pumping Lemma for regular sets. Show that the set L={a | p is a prime} is
not regular.
(b) Discuss closure properties i.e. concatenation, union, intersection, complement
of regular languages.
5. Attempt any one part of the following: 7x1=7
(a) Discuss inherent ambiguity of context free languages with suitable example.
Construct the context free grammar that accepts language L={aibjck| i = j or j =
k; i, j, k are positive integers}.
(b) Define parse tree. Find parse tree for the string abbcde considering the
productions-
SaAcBe
AAb
Ab
Bd
Is this ambiguous? Justify.
6. Attempt any one part of the following: 7x1=7
(a) Differentiate between deterministic PDA (DPDA) and non-deterministic PDA
(NPDA) with suitable example. Also discuss two stack PDA with example.

WWW.AKTutor.in
Downloaded by IT33_075_SAPAN GHAI (sapanghai297@gmail.com)
lOMoARcPSD|21665779

(b) Construct a PDA equivalent to the following CFG productions:


S→aAA, A→aS│bS│a

7. Attempt any one part of the following: 7x1=7


(a) Write short notes on the following:
(i) Halting problem of Turing machine
(ii) Recursive Language
(iii) Variants of Turing Machine
(b) Define Post’s Correspondence Problem (PCP) and Modified PCP with its
applications. Find any three PCP solutions of the lists x=(b,bab3,ba) and
y=(b3,ba,a).

WWW.AKTutor.in
Downloaded by IT33_075_SAPAN GHAI (sapanghai297@gmail.com)
lOMoARcPSD|21665779

RCS403

Printed Pages: 02 Sub Code: RCS403


Paper Id: 110257 Roll No.
B TECH
(SEM-IV) THEORY EXAMINATION 2018-19
THEORY OF AUTOMATA AND FORMAL LANGUAGES

Time: 3 Hours Total Marks: 70


Note: Attempt all Sections. If require any missing data; then choose suitably.

SECTION A

1. Attempt all questions in brief. 2 x 7 = 14


a. For the given language L1 = ε, L2 = {a}, L3 = Ø. Compute L1 L2* U L3*.
b. Design a FA to accept the string that always ends with 101.
c. Write regular expression for set of all strings such that number of a’s divisible
by 3 over Σ = {a,b}
d. Construct the CFG for the Language L = {a2nbn |n>=3}.
e. What do you mean by ε-Closure in FA?
f. Explain Universal TM.

A
g. Explain Two Stack PDA.

PT
SECTION B

2. Attempt any three of the following:


U 7 x 3 = 21
G

.2
a. Construct a minimum state DFA from given FA
AR

62
M

5.
KU

11
5.
Y

|4
JA

7
VI

2
7:
R

:5
D

Fig. 1
08

b. Find the regular expression corresponding to the finite automata given bellow:
9
01
-2
ay
M
4-
|1

Fig. 2

P.T.O

Page 1 of 2

WWW.AKTutor.in
DR VIJAY KUMAR GUPTA | 14-May-2019 08:57:27 | 45.115.62.2
Downloaded by IT33_075_SAPAN GHAI (sapanghai297@gmail.com)
lOMoARcPSD|21665779

RCS403

c. Convert the following CFG to its equivalent GNF:


S → AA | a, A → SS | b.
d. Design a PDA for the following language:
L = {aibjck | i = j or j = k}
e. Design a TM for the following language:
L = { an+2bn | n >0 }

SECTION C
3. Attempt any one part of the following: 7x1=7
(a) Design FA for ternary number divisible by 5.
(b) Explain Myhill-Nerode Theorem using suitable example.

4. Attempt any one part of the following: 7x1=7


n n
(a) Prove that the following Language L = {a b } is not regular
(b) Explain the Closure properties of regular expression.

A
5. Attempt any one part of the following: 7x1=7

PT
(a) Design the CFG for the following language:
i) L = {0m1n | m ≠ n & m,n ≥ 1}
U
G
ii) L = {albmcn | l + m = n & l,m ≥ 1}

.2
Prove that the following Language L = {anbncn} is not Context Free.
AR

(b)

62
M

5.
6. Attempt any one part of the following: 7x1=7
KU

11
R *
(a) Design a PDA for the Language L ={WW | W={a,b} }
(b) Generate CFG for the given PDA M is defined as
5.
Y

|4
M = ({q0, q1}, {0,1} {x, z0}, δ, q0, z0, q1) where δ is given as follows:
JA

δ (q0,1, z0) = (q0, xz0)


7
VI

δ (q0,1, x) = (q0, xx)


2

δ (q0,0, x) = (q0, x)
7:
R

δ (q0, ε, x) = (q1, ε)
:5
D

δ (q1, ε, x) = (q1, ε)
08

δ (q1,0, x) = (q1, xx)


9

δ (q1,0, z0) = ( q1, ε)


01

7. Attempt any one part of the following: 7x1=7


-2
ay

(a) Design a TM for the following language:


L = { anbncn | n≥ 1}
M

(b) Write short note on:


4-

i) Recursive Language and Recursively Enumerable Language.


|1

ii) PCP problem and Modified PCP Problem

Page 2 of 2

WWW.AKTutor.in
DR VIJAY KUMAR GUPTA | 14-May-2019 08:57:27 | 45.115.62.2
Downloaded by IT33_075_SAPAN GHAI (sapanghai297@gmail.com)
Printed Page: 1 of 2
lOMoARcPSD|21665779

Subject Code: KCS402


0Roll No: 0 0 0 0 0 0 0 0 0 0 0 0 0

BTECH
(SEM IV) THEORY EXAMINATION 2021-22
THEORY OF AUTOMATA AND FORMAL LANGUAGES

Time: 3 Hours Total Marks: 100


Note: Attempt all Sections. If you require any missing data, then choose suitably.

SECTION A
1. Attempt all questions in brief. 2x10 = 20
Q.no Questions Marks CO
(a) Define Alphabet and String in Automata Theory. 2 2
(b) Give the definition of Deterministic Finite Automaton (DFA). 2 1
(c) Explain in brief about the Kleen’s Theorem. 2 2
(d) Define Context Free Grammar (CFG). 2 1
(e) Write the Context Free Grammar (CFG) for regular expression (0+1)* 2 3
(f) What are Right Linear grammar and Left Linear grammars? 2 3
(g) Discuss briefly about the Push Down Automata (PDA). 2 4
(h) What do you mean by Two stack Pushdown Automata? 2 4
(i) What do you mean by basic Turing Machine Model? 2 5
(j) What do you understand by the Halting Problem? 2 5
90

2
SECTION B

13
2. Attempt any three of the following: 10x3 = 30
_2

Q.no Questions Marks CO

2.
P2

(a) Explain in detail about the Turing Church’s Thesis and Recursively 10 5

24
Enumerable languages.
2E

5.
(b) Prove that the Compliment, Homomorphism, Inverse Homomorphism, 10 2
.5
P2

and Closure of a Regular Language is also Regular.


17
(c) Give the Complete description about the Chomsky Hierarchy. 10 3
Q

|1

(d) Convert the grammar S  aAA, A  a |aS| bS to a PDA that accepts 10 4


the same language by Empty stack.
54

(e) Grammar G is given with the production S->aSS A->b. Compute the 10 1
8:

string w= aababbb with the Left most and Right most derivation Tree.
:2

SECTION C
13

3. Attempt any one part of the following: 10x1 = 10


2

Q.no Questions Marks CO


02

(a) Write short notes on following. 10 5


-2

i) Turing Machine as Computer of Integer Functions


08

ii) Universal Turing machine


(b) Explain in detail about the Pumping Lemma and application of 10 2
0-

Pumping Lemma for Regular Languages.


|1

4. Attempt any one part of the following: 10x1 = 10


Q.no Questions Marks CO
(a) Construct a Non Deterministic Finite Automation (NFA) for the 10 1
language L which accepts all the strings in which the third symbol
from right end is always 'a' over  = {a, b}.
(b) Explain in detail about the Myhill-Nerode theorem using suitable 10 3
example.

WWW.AKTutor.in
QP22EP2_290 | 10-08-2022 13:28:54 | 117.55.242.132
Downloaded by IT33_075_SAPAN GHAI (sapanghai297@gmail.com)
Printed Page: 2 of 2
lOMoARcPSD|21665779

Subject Code: KCS402


0Roll No: 0 0 0 0 0 0 0 0 0 0 0 0 0

BTECH
(SEM IV) THEORY EXAMINATION 2021-22
THEORY OF AUTOMATA AND FORMAL LANGUAGES

5. Attempt any one part of the following: 10x1 = 10


Q.no Questions Marks CO
n n
(a) Prove that the following Language L = {a b : n>=0} is not a regular 10 4
language.
(b) Design a Turing Machine for the language L. Where, L={anbncn| n≥1} 10 5

6. Attempt any one part of the following: 10x1 = 10


Q.no Questions Marks CO
(a) Prove that the Compliment, Homomorphism, Closure and Inverse 10 2
Homomorphism of a Regular language is also Regular.
(b) Minimize the given DFA shown below (Figure A). 10 1

90

2
13
_2

2.
P2

24
2E

5.
Figure A
.5
P2

17
Q

7. Attempt any one part of the following: 10x1 = 10


|1

Q.no Questions Marks CO


(a) Explain in detail about the following. 10 4
54

i) Closure properties of Regular Languages


8:

ii) Decidability- Decision properties of Regular Languages


:2

(b) Check whether the grammar is ambiguous or not. 10 3


13

R-> R+R/ RR/ R*/ a / b / c. Obtain the string w = a+b*c


2
02
-2
08
0-
|1

WWW.AKTutor.in
QP22EP2_290 | 10-08-2022 13:28:54 | 117.55.242.132
Downloaded by IT33_075_SAPAN GHAI (sapanghai297@gmail.com)

You might also like