Theory of Automata

Question Code:
MARCH-2023
THEORY OF AUTOMATA
TIME ALLOWED: 2.5 HRS FULL MARKS: 60
Answer to question no. 1 of group A is compulsory and to be answered first .this answer is to be made in
separate loose script(s) provided for the purpose. Maximum time allowed is 30 minutes ,after which the loose answer
scripts will be collected and fresh answer scripts for answering the remaining part of the question will be provided .On
early submission of answer scripts of Question no.1 ,a student will get the remaining script earlier.
Answer any five (05) Questions from Group B.
____________________________________________________________________________
GROUP-A
1. Choose the correct answer from the given alternatives (any twenty): 1X20
i) Which of the following is not a part of 5-tuple finite automata?

a) Input alphabet
b) Transition function
c) Initial State
d) Output Alphabet
ii) In mealy machine, the O/P depends upon

a) Present state
b) Next state
c) State and Input
d) Only Input
iii) Which of the following is an application of Finite Automaton?

a) Compiler Design
b) Grammar Parsers
c) Text Search
d) All of the mentioned
iv) Type 2 language is accepted by

a) LBA
b) PDA
c) Finite Automata
d) Turing Machine
v) Transition function maps.

a) Σ * Q -> Σ
b) Q * Q -> Σ
c) Σ * Σ -> Q
d) Q * Σ -> Q
vi) Language of finite automata is

a) Type 0
b) Type 1
c) Type 2
d) Type 3
vii) Type 1 language is accepted by
a) LBA
b) PDA
c) Finite Automata
d) Turing Machine
viii) A turing machine that is able to simulate other turing machines is

a) Nested Turing machines
b) Universal Turing machine
c) Counter machine
d) None of the mentioned
ix) The production of form: non-terminal -> ε is called

a) Sigma Production
b) Null Production
c) Epsilon Production
x) A push down automaton employs ________ data structure.

a) Queue
b) Linked List
c) Hash Table
d) Stack
xi) Which of the following is true?
a) All NFA are DFA
b) Both DFA and NFA are equal to each other
c) All DFA are NFA
d) NFA and DFA have different power
xii) Turing Machine is a model of

a) 4 tuples
b) 6 tuples
c) 7 tuples
d) 8 tuples
xiii) Recursively Enumerable Language is also known

a) type 0
b) type 1
c) type 2
d) type 3
xiv) A grammar that generates two different parse trees for the same input string is known as
a) left recursive
b) ambiguous
c) right linear
d) left factored
xv) Which of the given grammar has unit production?

a) S->Sa,S->b
b) S->aSb,S->ab
c) S->aSb,S->epsilon
d) S->B,B->b
xvi) The classification of 4 types of grammar was given by
a) Ritchie
b) Gosling
c) Hopper
d) Chomsky
xvii) Which of the following option is correct?

a) NFA is slower to process and its representation uses more memory than DFA
b) DFA is faster to process and its representation uses less memory than NFA
c) NFA is slower to process and its representation uses less memory than DFA
d) DFA is slower to process and its representation uses less memory than NFA
xviii) NPDA stands for
a) Non-Deterministic Push Down Automata
b) Null-Push Down Automata
c) Nested Push Down Automata
xix) Moore Machine is a model of

a) 4 tuples
b) 5 tuples
c) 6 tuples
d) 7 tuples
xx) Which of the following is Finite Automata with output?

a) Mealy Machine
b) Moore Machine
c) Both a and b
d) Turing Machine
xxi) Which of the following statements is true?

a) NFA does not have epsilon transition
b) In a DFA there is only one final state always
c) A CFG has 4 tuples
d) A CFG production can have two symbols on left hand side
xxii) The first step of CNF conversion is

a) To reduce no. of non-terminals on right side
b) To check whether there is null production and unit production in the grammar or not
c) To check ambiguity
d) To remove left-recursion
xxiii) The context free languages are closed under
a) Union
b) Concatenation
c) Kleene Star
d) All of the above
xxiv) Which among the following is the root of the parse tree?
a) Production P
b) Terminal T
c) Variable V
d) Starting Variable S
xxv) A turing machine operates over

a) finite memory tape
b) infinite memory tape
c) depends on the algorithm
d) none of the mentioned
GROUP-B
Answer any five questions from the following questions: 8X5
2. a) Convert the following NFA into its equivalent DFA:
b) Differentiate between Mealy Machine and Moore Machine. 6+2
3.a) State and prove Arden’s Theorem.

b) Explain Chomsky Hierarchy with diagram. 4+4
4. Convert the following Mealy Machine into its equivalent Moore Machine:
5. a) Convert the regular expression (a+b)*abb into NFA.

b) Construct a DFA that will accept any binary string ending with 00. 4+4
6. Find out the regular expression corresponding to the following Finite Automata.
8
7. a) Prove that the following grammar is ambiguous and remove ambiguity from the following grammar:
E -> E+E
E -> E*E
E -> id
b) Differentiate between type 2 and type 3 grammar. 6+2
8. Convert the following grammar to CNF form:
S → a | aA | B
A → aBB | ε
B → Aa | b 8
9. Derive the string "aabbabba" for leftmost derivation, rightmost derivation and build derivation tree using a
CFG given by:
S → aB | bA
A → a | aS | bAA
B → b | bS | aBB 8
10. a) Define a PDA mathematically.

b) Discuss working principle of Turing Machine with diagram. 3+5
11. a) Convert the following Moore Machine to Mealy Machine:
Present state Next State Output

Input = 0 Input = 1
→a d
b 0
b a d 1
c b c 0
d b a 1
b) Write at least four differences between DFA and NFA. 6+2

Theory of Automata

Uploaded by

Copyright:

Available Formats

Theory of Automata

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Theory of Automata

Uploaded by

Copyright:

Available Formats

Question Code:

i) Which of the following is not a part of 5-tuple finite automata?

ii) In mealy machine, the O/P depends upon

iii) Which of the following is an application of Finite Automaton?

iv) Type 2 language is accepted by

v) Transition function maps.

vi) Language of finite automata is

viii) A turing machine that is able to simulate other turing machines is

ix) The production of form: non-terminal -> ε is called

x) A push down automaton employs ________ data structure.

xii) Turing Machine is a model of

xiii) Recursively Enumerable Language is also known

xv) Which of the given grammar has unit production?

xvii) Which of the following option is correct?

xix) Moore Machine is a model of

xx) Which of the following is Finite Automata with output?

xxi) Which of the following statements is true?

xxii) The first step of CNF conversion is

xxv) A turing machine operates over

Answer any five questions from the following questions: 8X5

2. a) Convert the following NFA into its equivalent DFA:

b) Differentiate between Mealy Machine and Moore Machine. 6+2

3.a) State and prove Arden’s Theorem.

5. a) Convert the regular expression (a+b)*abb into NFA.

b) Differentiate between type 2 and type 3 grammar. 6+2

8. Convert the following grammar to CNF form:

10. a) Define a PDA mathematically.

11. a) Convert the following Moore Machine to Mealy Machine:

Present state Next State Output

You might also like