FINAL TERM
EXAMINATION
CS402- Theory of
Automata (Session - 1)
Question No: 1 ( Marks: 1 ) - Please choose one
If
r1 = (aa + bb) and r2 = ( a + b) then the language (aa + bb)(a + b) will be
generated by
► (r1)(r2)
*► (r1 + r2)
► (r2)(r1)
► (r1)*
Question No: 2 ( Marks: 1
) - Please choose one
“One
language can be expressed by more than one FA”. This statement is ______
* ► True
► False
► Some times true & sometimes false
► None of these
Question No: 3 ( Marks: 1 ) - Please choose one
Who
did not invent the Turing machine?
► Alan Turing
*► A. M. Turing
► Turing
► None of these
Question No: 4 ( Marks: 1 ) http://vustudents.ning.com - Please
choose one
Which
statement is true?
*► The tape
of turing machine is infinite.
► The tape of turing machine is finite.
► The tape of turing machine is infinite
when the language is regular
► The tape of turing machine is finite
when the language is nonregular.
Question No: 5 ( Marks: 1 ) - Please choose one
A
regular language:
*► Must be finite
► Must be infinite
► Can be finite or infinite
► Must be finite and cannot be infinite
Question No: 6 ( Marks: 1 ) - Please choose one
Every
regular expression can be expressed as CFG but every CFG cannot be expressed as
a regular expression. This statement is:
► Depends on the language
► None of the given options
*► True
► False
Question No: 7 ( Marks: 1 ) - Please choose one
Above
given FA corresponds RE r. then FA corresponding to r* will be
This statement is
*► True
► False
► Depends
on language
► None
of these
Question No: 8 ( Marks: 1 ) http://vustudents.ning.com- Please choose one
Consider
the language L of strings, defined over Σ = {a,b}, ending in a
► There are finite many
classes generated by L, so L is regular
*► There are infinite many classes generated by L, so L
is regular
► There are finite many
classes generated by L, so L is non-regular
► There are infinite
many classes generated by L, so L is non-regular
Question No: 9 ( Marks: 1 ) - Please choose one
Above
given TG has _____________ RE.
► (aa+aa+(ab+ab)(aa+ab)*(ab+ba))*
*►
(aa+bb+(ab+ba)(aa+bb)*(ab+ba))*
► (aa+bb+(ab+ba)(aa+bb)(ab+ba))*
► None of these
Question No: 10 ( Marks: 1 ) - Please choose one
The word ‘formal’ in formal
languages means
*► The symbols used have well defined meaning
► They are unnecessary, in reality
► Only the form of the string of symbols
is significant
► None of these
Question No: 11 ( Marks: 1 ) - Please choose one
Let
A = {0, 1}. The number of possible strings of length ‘n’ that can be formed by
the elements of the set A is http://vustudents.ning.com
► n!
*► n2
► nm
► 2n
Question No: 12 ( Marks: 1 ) - Please choose one
Choose the correct statement.
► A Mealy machine generates no language as such
► A Moore machine generates no language
as such
*► A Mealy machine
has no terminal state
► All of these
Question No: 13 ( Marks: 1 ) - Please choose one
TM is more powerful than FSM
because
► The tape movement is confined to one direction
*► It has no finite
state control
► It has the capability to remember
arbitrary long sequences of input symbols
► None of these
Question No: 14 ( Marks: 1 ) - Please choose one
If
L1 and L2 are expressed by regular expressions r1 and r2, respectively then the language expressed
by r1 + r2 will be _________
* ► Regular
► Ir-regular
► Can’t be decided
► Another Language which is not listed
here
Question No: 15 ( Marks: 1 ) - Please choose one
Like
TG, a PDA can also be non-deterministic
► True
*► False
Question No: 16 ( Marks: 1 ) - Please choose one
The above machine is a/anTG
___________ http://vustudents.ning.com
► Finite Automata
*► Turing machine
► FA
► TG
Question No: 17 ( Marks: 1 ) - Please choose one
The
language of all words (made up of a’s and b’s) with at least two a’s can not be
described by the regular expression.
► a(a+b)*a(a+b)*(a+b)*ab*
► (a+b)* ab* a(a+b)*
► b*ab* a(a+b)*
► none of these
Question No: 18 ( Marks: 1 ) - Please choose one
In
FA, if one enters in a specific state but there is no way to leave it, then
that specific state is called
*► Dead State
► Waste Basket
► Davey John Locker
► All of these
Question No: 19 ( Marks: 1 ) - Please choose one
If L
is a regular language then, Lc is also a _____ language.
*► Regular
► Non-regular
► Regular but finite
► None of the given
Question No: 20 ( Marks: 1 ) - Please choose one
In
CFG, the symbols that can’t be replaced by anything are called___
► Terminal
► Non-Terminal
*► Production
► All of given
Question No: 21 ( Marks: 1 ) - Please choose one
Which
of the following is NOT a regular language? http://vustudents.ning.com
► String of 0’s whose length is a
perfect squere
*►
Set of all palindromes made up of 0’s and 1’s
► String of 0’s whose length is a prime
number
► All of the given options
Question No: 22 ( Marks: 1 ) - Please choose one
Choose
the incorrect (FALSE) statement.
► A Mealy machine generates no language
as such
► A Mealy machine has no terminal state
*► For a given input string,
length of the output string generated by a Moore machine is not more than the
length of the output string generated by that of a Mealy machine
► All of these
Question No: 23 ( Marks: 1 ) - Please choose one
Pumping
lemma is generally used to prove that:
► A given language is infinite
*► A given language is not
regular
► Whether two given regular expressions
of a regular language are equivalent or not
►
None of these
Question No: 24 ( Marks: 1 ) - Please choose one
Which
of the following is a regular language?
► String of odd number of zeroes
► Set of all palindromes made up of 0’s
and 1’s
*► String of
0’s whose length is a prime number
► All of these
Question No: 25 ( Marks: 1 ) - Please choose one
Choose
the incorrect statement:
► (a+b)*aa(a+b)* generates Regular
language.
► A language consisting of all strings
over ∑={a,b} having equal number of a’s and b’s
is a regular language
► Every language that can be expressed
by FA can also be expressed by RE
► None of these
Question No: 26 ( Marks: 1 ) - Please choose one
Left
hand side of a production in CFG consists of:
► One terminal
► More than one terminal
► One non-terminal
* ► Terminals and
non-terminals
Question No: 27 ( Marks: 2 )
Diffrentiate
between Regular and Non regular languages?
Ans:
The main difference between
regular and non regular language are as:
1. The regular language is that
language which can be expressed by RE is known as regular language whereas any
language which can not be expressed by RE is known as non regular language.
Question No: 28 http://vustudents.ning.com ( Marks: 2 )
What
is meant by a "Transition" in FA?
Question No: 29 ( Marks: 2 )
What
are the halt states of PDAs?
Ans:
There are some halts states
in PDA which are as:
- Accept or reject stat is also halt state.
- Reject state is like dead non final state.
- Accept state is like final state.
Question No: 30 ( Marks: 2 )
Identify
the null productions and nullable productions from the following CFG:
S
-> ABAB
A
-> a | /\
B->
b | /\
Question No: 31 ( Marks: 3 )
Describe
the POP operation and draw symbol for POP state in context of Push down stack.
Question No: 32 ( Marks: 3 )
What
does the the following tape of turing machine show?
Ans:
Arbitrary Summary Table:
The
arbitrary summary table shows the trip
from READ9 to READ3 does not pop one
letter
form the STACK it adds two letters to the
STACK.
Row11 can be concatenated with some other net style
sentences e.g. row11 net(READ3, READ7, a)Net(READ7, READ1, b)Net(READ1,
READ8, b) it gives the non terminal Net(READ9, READ8, b),
The whole process can be written as:
Net(READ9,
READ8, b) ?Row11Net(READ3, READ7,a) Net(READ7, READ1,
b)Net(READ1, READ8, b)
This
will be a production in the CFG of the corresponding row language.
Question No: 33 ( Marks: 3 )
Find Pref (Q in R) for:
Q = {10, 11, 00, 010}
R
= {01001, 10010, 0110, 10101, 01100, 001010}
Question No: 34 ( Marks: 5 )
Consider the Context Free Grammar (CFG)
S à 0AS | 0
A à S1A | SS | 1a
Show
that the word 0000100 can be generated by
this CFG by showing the whole derivation starting from S
Question No: 35 ( Marks: 5 )
Consider
the language L which is EVEN-EVEN, defined over
Σ = {a,b}. In how many classes does L may partition Σ*.
Explain briefly.
Question No: 36 ( Marks: 5 )
What are the conditions (any five) that must be met to know
that PDA is in conversion form? http://vustudents.ning.com
Ans:
Conversion form of PDA:
A PDA is in conversion form if it has following conditions:
1. The PDA must begin with the sequence
2. There is only one ACCEPT state.
3. Every edge leading out of any READ or
HERE state goes directly
into a POP state.
4. There are no REJECT states.
5. All branching, deterministic or nondeterministic occurs at READ or
HERE states.
6. The STACK is never popped beneath this $ symbol.
7. No two POPs exist in a row on the same path without a READ or
HERE.
8. Right before entering ACCEPT this symbol is popped out and
left.
No comments:
Post a Comment