Finite Automaton (FA) has:
A.Zero or more final states
B. Exactly one final state
C. Not more than two final states
D. Exactly two final states
The formal language is also known as _________.
A. Semantic language
B. Informal language
C. Syntactic language
D. Normal language
The language of all strings defined over alphabet set = {x,
y} having triple
x’s or triple y’s will have the minimum strings with length
of:
A. 1
B. 3
C. 4
D. 2
If an alphabet has "2" number of letters, then
total number of strings of
length "3" will be ________.
A. 5
B. 9
C. 8
D. 6
GTG for the expression (a+b)*bb may have minimum number of
states:
A. 3
B. 4
C. 2
D. 1
Consider the Regular Expression (RE) a (a + b)b*. Which one
of the
following is NOT accepted by the provided RE?
A. aa
B. aab
C. aba
D. abb
Which of the following is NOT true about the term alphabet?
A.It is usually denoted by Greek letter sigma
B. It can be an empty set
C. Strings are generated by concatenating its elements
D.It is a finite set of symbols
Which of the following is free of non-determinism?
A. FA
B. TG
C. NFA
D. NFA-^
The language of all strings defined over alphabet set = {a,
b} containing
‘bbb’ will have the minimum string with length of:
A. 1
B. 2
C. 3
D. 4
The aa(a+b)*bb is the RE of the language defined over
Σ={a,b}.The
language must ____________.
A. have at least two ab
B. have at least one aa and one bb
C. have at least one abbb
D. have at least one ba
Reverse of string "YxwzYz" defined over Σ
={w,x,Y,z} is __________.
A. zYzwxY
B. zYzxwY
C. zYwzxY
D. zYzwYx
If "r1" and "r2" are regular
expressions, then which of the following is not
a regular expression?
A.r1 + r2
B. r1*
C. r1 r2
D. r1 – r2
Which of the following string belongs to the language of the
regular
expression (aa*b)*?
A. baabab
B. aabaab
C. aaaaaa
D. abbbaa
FA of EVEN-EVEN language shows that it accepts the null
string by
declaring the _________ as a __________as well.
A.Initial state, final state
B. Initial sate, null state
C. Final state, initial state
D. Final state, null state
Let S = {a, bb, bab, baabb} be a set of strings, which one
of the following
will not be included in S*?
A. baba
B. bbbaabaabb
C. baabbabb
D. bbaaabb
The language of all strings defined over alphabet set = {x,
y} that ends
with different letters will have the maximum length of:
A. 1
B. 2
C. infinite
D. 3
In an FA, when there is no path from the initial state to
final state, then
that FA_____________.
A. accept all non empty strings
B. does not accept any string
C. accept all strings
D. accept null strings
If Σ= {a, b, c, d}. How many transitions will be there on
each state of a
finite automaton for any language defined over Σ?
A. 2
B. 4
C. 1
D. 3
Which of the following is the minimal number of states for a
finite
automaton accepting the language of all strings defined over
any alphabet
set?
A. 3
B. 4
C. 2
D. 1
How many states of a finite automaton will be final for
accepting L = {^,
b, bb, bbb}?
A. 3
B. 1
C. 4
D. 2
There is no compulsion that each state must have an on
outgoing edge for
every input variable in:
A. Transition Graph
B. Transition Table
C. Both Finite Automata and Transition Graph
D. Finite Automata
In TG, there can be more than one _____________.
A.start state only
B. null state only
C. start state and final state
D.final state only
Substrings as input letters can be specified on edges in:
A. NFA
B. PDA
C. FA
D. TG
If we have the regular expression (a + b)*, then we can draw
FA for the
provided RE with minimum _________ number of state(s).
A. 2
B. 0
C. 1
D. 3
Question No:1 (Marks:1)
Σ={a,Aa,Abb}, then string aAaAbbAa has length.
A. One
B. Two
C. Three
D. Four Page 4
Question No:2 (Marks:1)
Languages generated by kleene star are always .
A. Finite
B. Infinite Page 7
C. Sometimes finite & sometimes infinite
D. None of the these
Question No:3 (Marks:1)
Let S = {aa, bb}, then S* will have the _______ string.
A. Λ Page 7
B. abba
C. aabbbaa
D. bbaab
Question No:4 (Marks:1)
If r1 = (aa + bb) and r2 = ( a + b) then the language (aa +
bb)* will be
generated by
A.(r1)(r2)
B. (r1 + r2)
C. (r2)*
D.(r1)* Page 10
Question No:5 (Marks:1)
If a language can be expressed through FA, then it can also
beexpressed
through TG.
A.True Page 25
B. False
Question No:6 (Marks:1)
If an alphabet has n number of letter, then number of
strings oflength m
will be
A. n+m
B. (n)(m)
C. m^n
D. n^m Page 6
Question No:7 (Marks:1)
In GTG, if a state has more than one incoming transitions
from a state.
Then all those incoming transitions can be reduced to one
transition using
sign
A.-
B. + Page 27
C. *
D.( )
Question No:8 (Marks:1)
Above given FA accepts strings defined over Σ={a , b}
A. All Page 15
B. Some
C. All but not null
D. None of these
Question No:9 (Marks:1)
One FA has 3 states and 2 letters in the alphabet. Then FA
will have
number of transitions in thediagram
A. 4
B. 5
C. 7
D. 6 Page 14
Question No:10 (Marks:1)
Every FA should be____________.
A. Deterministic Page 25
B. Non- Deterministic
C. Deterministic & Non- Deterministic
D. None of these
Question No:11 (Marks:1)
Auto Meta mean
A. Manual work
B. Automatic work Page 3
C. Both
D. None of these
Question No:12 (Marks:1)
NFA to FA will
A.Equal Page 43
B. Not equal
C. Not valid
D. None of given
Question No:13 (Marks:1)
The length of output string in case of is one more than the
length of
corresponding input string.
A. Finite Automaton Page 55
B. TG
C. GTG
D. NFA
Question No:14 (Marks:1)
The machine helps in building a machine that can perform the
addition
of binary numbers.
A.Incrementing Page 60
B. Complementing
C. Decrementing
D. None of the given
Question No:15 (Marks:1)
In proving Kleene Theorem II, if a state has two incoming
transition
edges labelled by RE from the same state, then replace all
the edges with
a single transition edge labelled by ------- of
corresponding RE.
A. Sum Page 27
B. Edge
C. FA
D.RE
Question No:16 (Marks:1)
Kleene Theorem III states that if the language can be
expressed by RE
then there exist -------- accepting the language.
A. FA Page 32
B. DFA
C. NFA
D. None
Question No:17 (Marks:1)
If L1 and L2′ are regular languages, L1 ∩ (L2′ U L1′)’ will
be
A. Regular Page 10
B. Ir-regular
C. Can’t be decided
D. Another Language which is not listed here
Question No:18 (Marks:1)
A regular language can be:
A. irregular
B. infinite
C. non-deterministic
D. None of the given options
Question No:19 (Marks:1)
There ______ a language for which only FA can be built but
not the RE.
A. is cannot be
B. is
C. may be
D. may not be
Question No:20 (Marks:1)
For every three regular expressions R, S, and T, the
languages denoted by
R(S U T) and (RS) U (RT) are the ______ .
A. Same
B. Different
C. R(S U T) is Greater
D. None of the given options
Question No:21 (Marks:1)
In _______ there must be transition for all the lettersof a
string.
A. NFA
B. GTG
C. TG
D. FA
Question No:22 (Marks:1)
We cannot construct an NFA for the language of ______
defined over
alphabet set {a,b}.
A. Even
B. odd
C. Palindromes
D.Integers
Question No:23 (Marks:1)
Decomposing a string into its valid units is referred as:
A. Decomposing
B. Splitting
C.Tokenizing
D. Dividing
Question No:24 (Marks:1)
Choose the correct word produced by RE (a + b)* (aa+bb).
A. Abab
B. Babab
C. aaaa
D. Ab
Question No:25 (Marks:1)
Considering FA1 and FA2 having 2 states each. Now FA1+FA2
can have
maximum ______________ number of states.
A. 2
B. 3
C. more than 3
D. None of these
Question No:26 (Marks:1)
If R is a regular language and L is some language, and L U R
is a _______,
then L must be a ________.
A. Regular language
B. Finite Auto
Question No:27 (Marks:1)
The minimum length of the strings(except null string) of a
language that
starts and ends in different letters will be:
A. 1
B. 2
C. 3
D. 4
Question No:28 (Marks:1)
Consider we have languages L7 and L6. Which of the following
represents their concatenation?
A.L7+L6
B. L7/L6
C. L6L7
D. L7L6
Question No:29 (Marks:1)
Let FA1 has x number of states and FA2 has y number of
states. Now
FA1+FA2 can have maximum _______________ number of states.
A. x+y
B. x-y
C. x/y
D. None
Question No:30 (Marks:1)
The language {a ab aba bab} is _____ .
A.Irregular
B. Regular
C. Recursive
D. None of the given options
Question No:31 (Marks:1)
If we have a finite language and the number of states in the
FA is n then
the maximum number of letters in the each word of the
language that will
be accepted by the given FA will be:
A. N
B. n-1
C. n+1
D. 1
Question No:32 (Marks:1)
Moore machine can have -------- final states.
A. 2
B. 4
C. 6
D. 8
Question No:33 (Marks:1)
There _______ be dead states in NFA.
A. may not
B. must
C. should not
D. will
Question No:34 (Marks:1)
Let L be the language of all strings, defined over ∑ =
{0,1}, ending in 10.
Which of the following strings are distinguishable with
respect to L with
z being 0?
A. 010, 101
B. 111, 101
C. 001, 101
D. 111, 111
Question No:35 (Marks:1)
There ________ be a unique path for each valid string
(called a word) in
NFA.
A.May not
B. Must
C. Should not
D.Will
Question No:36 (Marks:1)
If we have only one state, having no transition for input
letters, then it is
an example of:
A.RE
B. FA
C. TG
D. NFA
Question No:37 (Marks:1)
Strings x,y,z belongs to Σ * such that xz ∈
L but yz ∉ L where L ⊆ Σ*
are:
A. Undetermined
B. Distinguishable
C. Indistinguishable
D.Both distinguishable and indistinguishable
Question No:38 (Marks:1)
A _______ with "n" states must accept at least one
string of length greater
than "n".
A. DFA
B. RE
C. Irregular language
D.Irrelevant language
Question No:39 (Marks:1)
In Moore machine, output is produced over the change of:
A. Transitions
B. Transitions and states
C. None of the mentioned
D. States
Question No:40 (Marks:1)
Keeping in view the discussion by Martin, how many states
are required
to recognize the language of all strings of length 3 or more
defined over
∑= {a,b}, with ‘a’ being the third letter from right?
A. 10
B. 12
C. 14
D. 16
Question No:41 (Marks:1)
Every _______ can be considered to be ______ as well, but
the converse
may not be true.
A. TG, FA
B. GTG
C. PDA
D. FA, TG Page 19
Question No:42 (Marks:1)
In the context of make NFA for the concatenation of FA1 and
FA2 (FA1
accepting null string), which of the following option is
correct?
A. Final states in both FAs
B. Initial states in both FAs
C. FA2 having initial state only
D. FA2 having final state only
Question No:43 (Marks:1)
In order to make NFA for the union of FA1 and FA2, the new
initial state
should be linked to:
A.Initial states of both FAs
B. Initial and final states of FA1 and FA2 respectively
C. Initial state of FA1 only
D. Final and initial states of FA1 and FA2 respectively
Question No:44 (Marks:1)
Keeping in view the discussion by Martin, how many states
are required
to recognize the language of all strings of length 2 or more
defined over
∑= {a,b}, with ‘b’ being the second letter from right?
A. 9
B. 6
C. 7
D. 8
Question No:45 (Marks:1)
If we have an NFA having 3 states, and we convert that NFA
to an FA.
The resultant FA will contains _______ states.
A. 1
B. 2
C. 3
D. 4
Question No:46 (Marks:1)
Let FA3 be an FA corresponding to FA1FA2, then initial state
of FA3
must correspond to the initial state of
A. FA1 only
B. FA2 only
C. FA1 and FA2
D. FA1 or FA2
Question No:47 (Marks:1)
In which of the following machine, the length of output
string is the same
to that of input string?
A.Mealy machine
B. Moore machine
C. Finite automaton with output
D. Non-deterministic finite automaton
Question No:48 (Marks:1)
Moore Machine is an application of:
A. None of the mentioned
B. Finite automata with output
C. Finite automata without input Google
D. Non- Finite automata with output
Question No:49 (Marks:1)
In NFA having multiple transitions at certain state, FA can
be built by
introducing:
A.Empty state
B. Combination of states
C. Initial state
D. Final state
Question No:50 (Marks:1)
In Mealy machine the output depends on __________________
A. Present state and Present input
B. Only present state
C. Nothing
D. Type of input
Question No:51 (Marks:1)
If L is a regular language, then (L’)’ U L will be:
A.L
B. C
C. P
D. F
Question No:52 (Marks:1)
A string will be accepted by an NFA if there exists _______
one
successful path.
A. Atleast
B. Atmost
C. Maximum
D. None of the given options
Question No:53 (Marks:1)
If A and B are regular languages, !(A’ U B’) is:
A. Non regular
B. May be regular
C. None of the mentioned
D. Regular
Question No:54 (Marks:1)
There is no question of accepting any language in:
A.Moore machine
B. FA
C. TG
D. GTG
Question No:55 (Marks:1)
In _______ there must be transitions for all the alphabets
over which a
language is defined.
A. FA
B. TG
C. NFA
D. GTG
Question No:56 (Marks:1)
Let FA3 be an FA corresponding to FA1FA2, then final state
of FA3 must
correspond to the final state of
A. FA2 only
B. FA1 only
C. FA1 or FA2
D. FA1 and FA2
Question No:57 (Marks:1)
How many new states are introduced while developing NFA for
the
closure of an FA?
A. 2
B. 4
C. 6
D. 8
Question No:58 (Marks:1)
Subtraction of binary numbers is possible through:
A.Both complementing and incrementing machine
B. Complementing machine
C. Incrementing machine
D.Converting machine
Question No:59 (Marks:1)
For a given Moore Machine, the input string is '101010',
thus the output
string would be of length:
A.Length of input string + 1
B. Length of input string – 1
C. Length of input string + 2
D. Length of input string -2
Question No:60 (Marks:1)
Which one of the following machine is represented as a
pictorial
representation with states and directed edges labeled by an
input letter
along with an output character?
A.Mealy machine
B. Moore machine
C. Finite state machine
D. Deterministic finite state machine
Question No:61 (Marks:1)
If FA1 corresponds to (a+b)* then FA1 must accept
___________
string/strings.
A. No
B. Odd length
C. Even length
D.Every
Question No:62 (Marks:1)
Closure of an FA is the same as ___________ of an FA with
itself
except that the initial state of the required FA is a final
state as well.
A. Sum
B. Union
C. Intersection
D. Concatenation
Question No:63 (Marks:1)
Given the language L = {ab, aa, baa}, which of the following
strings are
inL*?
abaabaaabaa
aaaabaaaa
baaaaabaaaab
baaaaabaa
A. 1, 2 and 3
B. 2, 3 and 4
C. 1, 2 and 4
D. 1, 3 and 4
Question No:64 (Marks:1)
FA and _______ are same except that _______ has unique
symbol for
each transition.
A. FA,TG
B. NFA,TG
C. NFA,FA
D. GTG,NFA
Question No:65 (Marks:1)
How many states of a finite automaton will be final for
accepting the only
string ‘abb’, if Σ= {a, b}?
A. 1
B. 2
C. 3
D. 4
Question No:66 (Marks:1)
Two machines are said to be equivalent if they print the
output string
when the input string is run on them.
A. Same, Same
B. Same, different
C. Different, same
D. Unique, different
Question No:67 (Marks:1)
Every NFA can be considered to be a -------- as well, but
the converse
may not be true.
A.TG
B. FA
C. GTG
D. PDA
Question No:68 (Marks:1)
In which of the following machine, the length of output
string is 1 more
than that of input string?
A. Mealy machine
B. Non-deterministic finite automaton
C. Finite automaton with output
D.Moore machine
Question No:69 (Marks:1)
If S = {aa, bb} then S* will not contain ___________.
A. abbbab
B. bbba
C. bbbbab
D. ababbb
Question No:70 (Marks:1)
Which of the following machine has only one initial state
and no final
state?
A.Moore machine
B. Finite state machine
C. Deterministic finite state machine
Question No:71 (Marks:1)
Which of the following diagram is very rigid in order to
express any
language?
A. TG
B. NFA
C. GTG
D. FA
Question No:72 (Marks:1)
If S = {a}, then S+ will be ___________.
A. {a, aaa, aaaa, aaaaa,…}
B. {a, aa, aaa, aaaa,…}
C. {a, aaa, aaaaa, aaaaaaa,…}
D. {aa, aaaa, aaaaaa, aaaaaaaa,…}
Question No:73 (Marks:1)
Let L be the language of all strings. defined over ∑ =
{0,1}. ending in 111.
Melay machine can have final states.
A.Zero
B. One
C. More than one but finite
D. More than one but infinite
Question No:74 (Marks:1)
Let’s we have two regular expressions R1=(xx+yy) and R2=(x+
y). Which
one of the following is the correct regular expression for
the Union of R1
and R2?
A.(xx+yy)(x+y)
B. (xx+yy)+(x+y)*
C.(xx+yy)+(x+y)
D.((xx+yy)+(x+y))*
Question No:75 (Marks:1)
The state where there is no way to leave after entry, is called_____________.
A. Davey John locker
B. initial state
C. final state
D. non-final state
Question No:76 (Marks:1)
Which one of the following word is not accepted by the given
regular
expression?
A. aaabab
B. aaaababb
C. abbaab
D. aabbabb
Question No:77 (Marks:1)
According to theory of automata there are _________ types of
languages.
A. One
B. Two
C.Three
D. Four
Question No:78 (Marks:1)
Regular languages are closed under the following operations.
A. Union only
B. Concatenation, Closure only
C. Union, Concatenation and Closure
Question No:79 (Marks:1)
Regular languages are closed under the following operations.
A. Union only
B. Concatenation, Closure only
C. Union, Concatenation and Closure
D.Regular languages are not closed under any operation
Question No:80 (Marks:1)
There can be more than _______ FA for a certain language but
for
_______ FA there is only one language associated with it.
A. one, one
B. one, two
C. two, three
D. two, one
Question No:81 (Marks:1)
There is one compulsion that each state must have an on
outgoing edge
forevery input variable in:
A. Finite Automata
B. Transition Graph
C. Both Finite Automata and Transition Graph
D. Transition Table
Question No:82 (Marks:1)
FA is also called
A. TG
B. GTG
C. NFA
D. DFA
Question No:83 (Marks:1)
If r1 and r2 are regular expressions then (r1 * r2) is
___________ .
A. FA
B. TG
C. GTG
D. RE
Question No:84 (Marks:1)
Keep in view the language of all strings ending with ‘a’
defined over Σ =
{a, b, c, d}. For which input letter, we will take a loop on
the final state
of its transition diagram?
A. a
B. b
C. c
D. d
Question No:85 (Marks:1)
Which of the following statements is true about NFA with
Null String?
A.Infinite states
B. Infinite set of letters
C. Infinite set of transitions
D.Transition of null string is allowed at any stage
Question No:86 (Marks:1)
Introducing new start state in case of multiple start states
is the step no.
of proving Kleene’s theorem part ||.
A. 1
B. 2
C. 3
D. 4
Question No:87 (Marks:1)
Which of the following diagrams expresses languages more
simply?
A. FA
B. NFA
C. TG
D. GTG
Question No:88 (Marks:1)
The language of all strings defined over alphabet set = {a,
b} that does not
end with ‘a’ actually ends with:
A. b
B. b and ^
C. ^
D. ^ and a
Question No:89 (Marks:1)
In NFA having no transition at certain state, FA can be
built by
introducing:
A.Empty state
B. Combination of states
C. Initial state
D. Final state
Question No:90 (Marks:1)
Formal is also known as
A. Syntactic language
B. Semantic language
C. Informal language
D. None of these
Question No:91 (Marks:1)
There may be more than one transition for a certain letter
on a state in:
A. Finite automata
B. Non-Deterministic Finite Automata
C. Transition Table
D. Moore Machine
Question No:92 (Marks:1)
FA of EVEN language shows null string when
A.Initial state is final as well
B. EVEN does not accept null
C. One state is declared null
D. None of the these
Question No:93 (Marks:1)
Which of the following statement is true about GTG?
A. Transitions are based on input letters
B. Transitions are based on specified substrings
C. Transitions are based on regular expressions
D. Transitions are based on alphabet set
Question No:94 (Marks:1)
In GTG, there can be more than one:
A. Start state
B. Final state
C. Start state and final state
D. Null state
Question No:95 (Marks:1)
GTG for the expression (aa+aba)* may have minimum number of
states:
A. 1
B. 2
C. 3
D. 4
Question No:96 (Marks:1)
In regular expressions, the operator ‘*’ stands for
A. Concatenation
B. Iteration
C. Selection
D. Add
Question No:97 (Marks:1)
If r1 is a regular expression then (r1)* is .
A. A generalized transition graph
B. A non-deterministic finite automaton
C. A finite automaton
D. Also, a regular expression
Question No:98 (Marks:1)
Which of the following is the bypass and state elimination
step in the
context of Kleene’s theorem part || proof?
A. 1
B. 2
C. 3
D. 4
Question No:99 (Marks:1)
Question No:100 (Marks:1)
Melay machine to increase the output string in magnitude by
1 is called:
A. Complementing machine
B. Incrementing machine
C. Decrementing machine
D.Converting machine
Question No:101 (Marks:1)
Kleene’s Theorem Part I expresses the relationship
between________.
A. FA and TG
B. TG and RE
C. RE and FA
D. FA and RE
Question No:102 (Marks:1)
Suppose we have FA3 (which is equal to FA1 + FA2), then the
final state
of FA3 will be declared final if:
A.It corresponds to final states of both FA1 and FA2
B. It corresponds to final states of FA1 only
C. It corresponds to final states of FA2 only
D.It corresponds to any of the final states in FA1 or FA2
Question No:103 (Marks:1)
Null strings can be specified on edges in:
A. Finite Automata
B. Non-Deterministic Finite Automata
C.Transition Graph
D. Melay Machine
Question No:104 (Marks:1)
What is false about the PALINDROME LANGUAGE?
A. Every word is reverse of itself.
B. It is an infinite language.
C. FA can be build for it.
D. None of the given option
Question No:105 (Marks:1)
While finding RE corresponding to TG, If TG has more than
one startstate
then
A.Introduce the new start state
B. Eliminate the old start state
C. Replace the old start stat with final state
D.Replace the old final state with new start state
Question No:106 (Marks:1)
All possible combinations of strings of a language including
null string is
referred as:
A.Concatenation of a language with itself
B. Kleene star closure of a language
C. Multiplication of language with itself
D. Addition of a language with itself
Question No:107 (Marks:1)
n! will be equal to:
A. n*n
B. n*(-n)!
C. n*(n-1)
D. n*(n-1)!
Question No:108 (Marks:1)
While finding RE corresponding to a TG, we connect the new
start state
with the old start state by transition.
A. a
B. b
C. Null
D.RE
Question No:109 (Marks:1)
In proving Kleene Theorem II, if three states are connected
then middle
state is removed by connecting first and third state and
writing
corresponding RE in:
A. Sum
B. Concatenation
C. Difference
D. Asterisk
Question No:110 (Marks:1)
In there must be transition for all the letters of a string.
A. NFA
B. GTG
C. TG
D. FA
Question No:111 (Marks:1)
There is no question accepting any language in:
A. FA
B. TG
C. GTG
D.Moore machine
Question No:112 (Marks:1)
The FA can be drawn for the regular expression (a+b)* with
minimum
state(s).
A. 1
B. 2
C. 3
D. 4
Question No:113 (Marks:1)
Which of the following does not contribute while finding out
the length of
strings?
A. ^
B. a
C. b
D. a+b
Question No:114 (Marks:1)
The language of all strings defined over alphabet set = {x,
y} that ends
with same letters will have the maximum length of:
A. 1
B. 2
C. 3
D.Infinite
Question No:115 (Marks:1)
Considering FA1 and FA2 states each. Now FA1+FA2 can have
maximum number of states.
A. 2
B. 3
C. More than 3
D. None of the given option
Question No:116 (Marks:1)
Which one of the following is the RE for the language
defined over Σ=
{a, b} having all the words starting with a?
A.(a + b)*
B. aa(a + b)+
C. a(a + b)*
D. a*(a + b)
Question No:117 (Marks:1)
An ___________ can be considered to be an intermediate
structure
between Finite automaton and Transition Graph.
A.RE
B. GTG
C. NFA
D. None of the given options
Question No:118 (Marks:1)
Suppose a language L1 has 2 states and L2 has 2 states. If
we have a
machine M that accepts L1 ∩ L2. Then, the total number of
states in M is
equal to _______.
A. 2
B. 4
C. 6
D. 8
Question No:119 (Marks:1)
FA corresponding to an NFA can be built by introducing a
state
corresponding to the combination of states, for a letter
having
A. No transition at certain state
B. One transition at certain state
C. Two transitions at certain state
D. More than two transitions at certain state
Question No:120 (Marks:1)
Automata is the plural of __________.
A. Automate
B. Automaton
C. Automation
D. Automatic
Question No:121 (Marks:1)
In NFA having no transition at certain. FA can be built by
introducing:
A.Empty state
B. Combination of states
C. Initial state
D. Final state
Question No:122 (Marks:1)
If S = { x }, then S* will be ___________.
A. {^,x,xxx,xxxx,xxxxx,…}
B. {^,x,xx,xxx,xxxx,…}
C. {^,x,xxx,xxxxx,xxxxxxx,…}
D. {^,xx,xxxx,xxxxxx,xxxxxxxx,…}
Question No:123 (Marks:1)
In TG, the string is supposed to be _____________ if there
is no path for
a string from initial to final state.
A. Accept null string
B. Accept all strings
C. Accept all non-empty strings
D. Does not accept any string
Question No:124 (Marks:1)
In Moore machine, if the length of input string is 9, then
the length of
output string will be:
A. 7
B. 8
C. 9
D. 10
Question No:125 (Marks:1)
When ODD language is expressed by an FA, then it will have
minimum
_______ states.
A. One
B. Two
C. Three
D. Four
Question No:126 (Marks:1)
[(a + b)(a + b)]*, given RE cannot generate the string
________.
A. abbaabab
B. abbbaa
C. bbbbbb
D. abbbaaaaa
Question No:127 (Marks:1)
The recursive method for defining a language has
______________ steps.
A. One
B. Two
C.Three
D. Four
Question No:128 (Marks:1)
Consider the following RE:
a(a + b)b*
All of the following words are accepted except .
A. aab
B. abb
C. aa
D. aba
Question No:129 (Marks:1)
For every three regular expressions R, S, T, the languages
denoted byR(S
ꓴ T) and (RS) ꓴ (RT) are the .
A. Same
B. Different
C. R(S ꓴ T) is greater
D. None of the given options
Question No:130 (Marks:1)
Alphabet S = {a, bc, cc} has number of letters.
A. One
B. Two
C.Three
D. Four
Question No:131 (Marks:1)
Two FAs are said to be equivalent, if they ______________.
A. Accept null string
B. Accept same language
C. Accept different language
D. None of the given options
Question No:132 (Marks:1)
------------ can also help in proving Kleene Theorem III.
A. NFA
B. PDA
C. Moore machine
D. Melay machine
Question No:133 (Marks:1)
Kleene’s Theorem Part II expresses the relationship between
_____.
A. FA and TG
B. TG and RE
C. RE and FA
D. FA and RE
Question No:134 (Marks:1)
If two RE’s generate same language then these RE’s are
called
___________.
A. Same RE
B. Equal RE
C. Similar RE
D.Equivalent RE
Question No:135 (Marks:1)
Every FA should be .
A. Deterministic
B. Non-deterministic
C. Deterministic and non-deterministic
D. Not depends on language
Question No:136 (Marks:1)
What statement is true?
A. A letter is always a combination of symbols
B. A letter may consist of one symbol
C. There is no difference between symbol and letter
D. Letters and symbols are the same thing
Question No:137 (Marks:1)
If ∑= {ab, bb}, then ∑* will not contain
A. abbbab
B. bbba
C. bbbbab
D. ababbb
Question No:138 (Marks:1)
Choose the correct word produced by RE (a + b)*ab.
A. abb
B. abab
C. bbbb
D. aaaa
Question No:139 (Marks:1)
According to 1st part of the Kleene’s theorem, If a language
can be
accepted by an FA then it can be accepted by a as well
A. FA
B. CFG
C. GTG
D.TG
Question No:140 (Marks:1)
“One language can be expressed by GTG”.
A. Only one
B. Only two
C. More than one
Question No:141 (Marks:1)
If a TG has more than one start states, then we can make a
single startstate
by introducing a new state and connecting it with all the
previously
existing start states by using.
A. Any infinite string
B. Single letter string
C. Null string
D. Any finite string
Question No:142 (Marks:1)
If in a NFA, ^ is allowed to be a label of an edge then that
NFA iscalled
.
A. TG
B. RE
C. NFA with null string
D.RE
Question No:143 (Marks:1)
If we want to make a Moore machine equivalent to mealy
machinethen
A.We should ignore the extra character printed by the Moore
machine.
B. We should ignore the extra character printed by the Mealy
machine.
C. We will make the initial state as a no carry state.
D.We should not ignore the extra character printed by the
Moore
machine.
Question No:144 (Marks:1)
Two machines are said to be equivalent if they print the
output string
when same input string is run no them.
A. Same
B. Different
C. Inverse
D. Null
Question No:145 (Marks:1)
The length of output in case of is one more than the length
of
corresponding input string
A. Moore machine
B. Mealy machine
C. Incremental machine
D. Adding machine
Question No:146 (Marks:1)
A is not a valid transition in
A. TG
B. GTG
C. NFA
D.RE
Question No:147 (Marks:1)
Dead states are also called
A.John Davey Lockers
B. Davey John Lockers
C. Mutex Lockers
D. Semaphores
Question No:148 (Marks:1)
Language of all strings whose length is odd and number of
y’s even
defined over alphabet set ∑ = {x, y} . will be accepted by
the given
language.
A. xxyxyxyyyx
B. xxyxyxyyyxy
C. xxyxyxyyyxx
D. xxyxyxyyy
Question No:149 (Marks:1)
If an effectively solvable problem has answer in Yes or NO.
then the
solution is called
A.Infinite problem
B. Decision procedure
C. Finite solution
D. Optimal procedure
Question No:150 (Marks:1)
If the intersection of two regular languages is regular then
thecomplement
of the intersection of these two languages is
A. Regular
B. Irregular
C. Irregular but finite
D.Irregular but infinite
Question No:151 (Marks:1)
If R is regular language and Q is any language
(regular/non-regular).
Then Pref( in ) is regular.
A. Q, Q
B. Q, R
C. R, Q
D.R, R
Question No:152 (Marks:1)
The strings or words which do not belong to a language are
called
of that language
A.Intersection
B. Union
C. Complement
D. Quotient
Question No:153 (Marks:1)
Prime is a language.
A. Finite
B. Both context free and regular
C. Regular
D. Non-regular
Question No:154 (Marks:1)
Finite Automaton (FA) must have number of states while
alanguage
has words.
A.Infinite, finite
B. Finite, finite
C. Finite, infinite
D.Infinite, infinite
Question No:155 (Marks:1)
The language “PRIME” is an example of language.
A.Regular but finite
B. Regular
C. Non regular but finite
D. Non regular Page 75
Question No:156 (Marks:1)
If L1 and L2 are regular languages then which statement is
NOT true?
A. L1 + L2 is always regular
B. L1 L2 is always regular
C.L1/L2 is always regular
D. L1* is always regular
Question No:157 (Marks:1)
If a language is regular it must generate number of
distinctclasses.
A. Finite
B. Infinite
C. Two
D. three
Question No:158 (Marks:1)
The operators like (* . +) in the parse tree are considered
as
A.Terminals
B. Non-terminals
C. Productions
D.Intermediates
Question No:159 (Marks:1)
Set of all palindromes over {a,b} is:
A.Regular
B. Regular and finite
C. Regular and infinite
D. Non-regular
Question No:160 (Marks:1)
Which one of the following languages is a non-regular
language?
A. Even-even
B. Containing double a
C. Start and end with same letter
D. Palindrome
Question No:161 (Marks:1)
The language of all strings partition ∑* into class(es).
A. One
B. Two
C. Three
D. Four
Question No:162 (Marks:1)
The language of all strings not beginning with ‘b’
partitions ∑* into
distinct classes.
A. Two
B. Three
C. Four
D. Five
Question No:163 (Marks:1)
The values of input (say a & b) do not remain same in
one cycle dueto
A. NAND gate
B. Clock pulse
C. OR gate
D. NOT gate
Question No:164 (Marks:1)
In a CFG, the non-terminals are denoted by
A. Small letters
B. Numbers
C. Capital letters
D. Small letters and numbers
Question No:165 (Marks:1)
a* + b* = (a + b)* this expression is
A. True
B. False
Question No:166 (Marks:1)
Length of EVEN-EVEN language is always_________.
A.Even
B. Odd
C. Sometimes even & sometimes odd
D. Such language doesn’t exist
Question No:167 (Marks:1)
While finding RE corresponding to TG, we connect the new
start stateto
the old start state by the transition labeled by
A. a
B. b
C. null
D. none of the given options
Question No:168 (Marks:1)
Given S, Kleene star closure is denoted by
A. S*
B. S+
C. SD. None of these
Question No:169 (Marks:1)
Which of the following steps replaces multiple incoming
transitionedges
with a single one in proving Kleene’s theorem part ||?
A. 1
B. 2
C. 3
D. 4
Question No:170 (Marks:1)
If r1 = (aa + bb) and r2 = (a + b) then the language (aa +
bb)(a + b) will
be generated by ____________.
A.(r1)(r2)
B. (r1 + r2)
C. (r2)(r1)
D.(r1)*
Question No:171 (Marks:1)
The language having even number of a’s and even number of
b’s
defined over S = {a, b} is called _______________.
A.EVEN-EVEN
B. ODD-ODD
C. PALINDROME
D. FACTORIAL
Question No:172 (Marks:1)
If L1’ and L2’ are regular languages. Then L1,L2 will be
A. Regular
B. Non regular
C. May be regular
D. None of the mentioned
Question No:173 (Marks:1)
f FA1 corresponding to (a+b)* then FA1 must accept
string/strings
A. No
B. Odd length
C. Even length
D.Every
Question No:174 (Marks:1)
In FA, initial state can be represented by:
A. Drawing an arrow head before that state
B. Drawing a circle in that state
C. leave the state empty
D. Drawing ‘+’ sign in that state
Question No:175 (Marks:1)
An FA is a collection of:
A. Finite states, finite transition and finite input letters
B. Infinite states, infinite transition and infinite input
letters
C. Only finite states and finite transitions
D. Only infinite states and infinite transitions
Question No:176 (Marks:1)
NFA with null string has ---------- initial state(s).
A. One
B. Two
C. Four
D. Three
Question No:177 (Marks:1)
The difference between number of states with regular
expression (a +b)
and (a + b)* is:
A. 0
B. 1
C. 2
D. 3
Question No:178 (Marks:1)
A transition graph is converted into a(n) in order to obtain
regular
expression.
A. FA
B. GTG
C. NFA
D. NFA
Question No:179 (Marks:1)
Consider the languages L1 = and L2 = {a}. Which one of
thefollowing
represents L1 L2* ꓴ L1*
A. ^
B. a*
C. All of the mentioned
D. None of the mentioned
Question No:180 (Marks:1)
If S = {a, b} then which of the following RE will generate
all possible
strings?
A. a* + b*
B. (ab)*
C.(a + b)*
D.(ab + ba)*
Question No:181 (Marks:1)
In drawing FA3 (which is equal to FA1 + FA2), a state will
bedeclared
final if
A.It corresponds to final states of both FA1 and FA2
B. It corresponds to final states of FA1
C. It corresponds to final states of FA2
D.It corresponds to any of the final states in FA1 or FA2
Question No:182 (Marks:1)
Let S = {a, bb, bab, baabb} be a set of strings, which one
of the following
will not be included in S*?
A. baba
B. baabbabb
C. bbaaabb
D. bbbaabaabb
Question No:183 (Marks:1)
The length of string “AbBAbcd” defined over Σ ={Ab,B,c,d} is
___________.
A. One
B. Two
C. Five
D. Four
Question No:184 (Marks:1)
In case of finite automaton there ________ be a transition
on each
_______ for every letter of the alphabet set.
A.Must, state
B. May be, state
C. Often, edge
D. Must, edge
Question No:185 (Marks:1)
Which one of the following word is not accepted by the given
regular
expression? (a+b)*(aaa+bbb)(a+b)*
A. Ababaaaab
B. Bababbbba
C.Baabaabba
D. Abbaaabba
Question No:186 (Marks:1)
1 Let FA1 accepts many strings and FA2 accepts none then
FA1+FA2
will be equal to:
A. FA1
B. FA2
C. FA2-FA1
D.(FA2)
Question No:187 (Marks:1)
Edges are expressed with a regular expression in:
A. GTG Page 23
B. FA
C. NFA
D. TG
Question No:188 (Marks:1)
NFA corresponding to union of FAs is built by introducing a
new start
state and connect it to the states originally connected to
the old start state
with the --------- transitions as the old start state:
A. Same
B. Union of
C. Different
D.Concatenated
Question No:189 (Marks:1)
---------- state is not important in Moore machine.
Final
Start
Question No:190 (Marks:1)
If we subtract a binary number 1010 from the binary number
1101(ignore
the overflow), then the result will be:
1100
0011
Question No:191 (Marks:1)
In concatenation, we include the initial state of FA2
automatically after
the final state of FA1 because of:
A.We need just two initial states
B. We need just one initial state
C.Some part of the string may be accepted by FA2
D.The strings of FA2 are accepted first before the strings
of
FA1
Question No:192 (Marks:1)
a(a+b)*b + b(a+b)*a is the regular expression of language
defined over
Σ={a,b} that is ________.
starting with a and ending in a
Question No:193 (Marks:1)
GTG for the expression (a+b)*bb may have minimum number of
states:
Aaabcbbcbacc
Question No:194 (Marks:1)
Which of the following state is introduced while developing
NFA for the
closure of an FA?
A. Final state
B. Simply an initial state
C. An initial state with loop for all letters
D. An initial state which should be final as well
Question No:195 (Marks:1)
In NFA,if null word (lambda) is allowed to be a label of an
edge, then that
NFA is called _________.
A. NFA with one string
B. NFA with two strings
C. NFA with null string
D.NFA without null string
Question No:196 (Marks:1)
Which one of the following is a correct word produced by the
RE
(a*b*)ab?
abab
Question No:197 (Marks:1)
While developing NFA for the union of FA1 and FA2, if there
is a loop
of ‘a’ at the initial state of FA1 then the new initial
state will have a
transition for ‘a’ that goes straight to:
A. the final state of FA1
B. The initial state of FA1
C. the initial state of FA2
D. the initial state of FA1*FA1
Question No:198 (Marks:1)
Let L be the language of all strings, defined over Σ =
{0,1}, ending in 111.
Which of the following strings are distinguishable with
respect to L with
z being 11?
111, 101
Question No:199 (Marks:1)
Which one of the following word is not accepted by the given
regular
expression?
abbbbaa
Question No:200 (Marks:1)
Which of the following is not a step-in elimination of
states procedure?
Unify single transitions to multi transitions that contains
union of
input
Question No:201 (Marks:1)
In Moore machine the output depends on
The state
Question No:202 (Marks:1)
While developing NFA for the union of FA1 and FA2, there
will be
The initial state of FA1
Question No:203 (Marks:1)
Let FA3 be an FA corresponding to FA1FA2, then the final
state of FA3
must correspond to the final state of
A. FA2 only
B.FA1 only
C.FA1 or FA2
D.FA1 and FA2
Question No:204 (Marks:1)
Let FA3 be an FA corresponding to FA1FA2, then the initial
state of FA3
must correspond to the initial state of
A. FA1 only
B. FA2 only
C.FA1 or FA2
D. FA1 and FA2
Question No:205 (Marks:1)
Mealy machine is equivalent to Moore machine, if we:
Applications of complementing and incrementing machines
Question No:206 (Marks:1)
In the context of make NFA for the concatenation of FA1 and
FA2 (FA2
accepting null string), which of the following option is
correct?
A.Final states in both FAs
B. Initial states in both FAs
C. FA2 having final state only
D. FA2 having initial state only
Question No:207 (Marks:1)
In the context of make NFA for the concatenation of FA1 and
FA2 (none
accepting null string), which of the following option is
correct?
A. No final state in FA2 only
B. No initial state in FA1 only
C. No final and initial states in FA1 and FA2 respectively
D. No initial and final states in FA1 and FA2 respectively
Question No:208 (Marks:1)
Let FA1 accepts many strings and FA2 accepts no string, then
FA1+FA2
will be equal to:
A. FA1
B. FA2
C. (FA2)*
D. FA2-FA1
Question No:209 (Marks:1)
The minimum length of the strings(except null string) of a
language that
starts and ends in the same letters will be:
A. 1
B. 2
C. 3
D. 4
Question No:210 (Marks:1)
While developing NFA for the union of FA1 and FA2, there
will be
_____________ transition/transitions for both ‘a’ and ‘b’ on
the new
initial state.
A. Single
B. Multiple
C. Only one
D. Only three
Question No:211 (Marks:1)
Which of the following form correctly expressed the regular
expression
RR*?
A. R+
B. RC. R*
D.R+R-
Question No:212 (Marks:1)
Which of the following is not a step in elimination of
states procedure?
A. Unifying all the final states into one using
e-transitions
B. Get the resulting regular expression by direct
calculation
C. Remove states until there is only starting and accepting
states
D. Unify single transitions to multi transitions that
contains union
of input
Question No:213 (Marks:1)
In the context of make NFA for the concatenation of FA1 and
FA2 (Both
FAs accepting null string), which of the following option is
correct?
A.Initial states in both FAs
B. Final states in both FAs
C. FA2 having initial state only
D. FA2 having final state only
Visit My YouTube
Channel
For More Important
Notes
Channel Name =
#VuTopperRM
Comments
Post a Comment
Please feel free to share your ideas.