Computer Science - Automata Theory – Multiple Choice Question

Question 1 of 70

1. Question

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 the above

Question 2 of 70

2. Question

Let A = {0, 1} The number of possible strings of length ‘n’ that can be formed by the elements of the set A is

n!
n²
nⁿ
2ⁿ

Question 3 of 70

3. Question

Choose the correct statements.

Moore and Mealy machines are FSM's with output capability.
Any given Moore machine has an equivalent Mealy machine.
Any given Mealy machine has an equivalent Moore machine.
Moore machine is not an FSM

Question 4 of 70

4. Question

The major difference between a Moore and a Mealy Machine is that

the output of the former depends on the present state and the current input
the output of the former depends only on the present state
the output of the former depends only on the current input
none of the above

Question 5 of 70

5. Question

Choose the correct statements.

A Mealy machine generates no language as such.
A Moore 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 one more than the length of the output string generated by that of a Mealy machine.

Question 6 of 70

6. Question

The recognizing capability of NDFSM and DFSM

may be different
must be different
must be the same
none of the above

Question 7 of 70

7. Question

FSM can recognize

any grammar
only CFG
any unambiguous grammar
only regular grammar

Question 8 of 70

8. Question

Pumping lemma is generally used for proving

a given grammar is regular
a given grammar is not regular
Whether two given regular expressions are equivalent
none of the above

Question 9 of 70

9. Question

Which of the following are not regular?

String of 0's whose length is a perfect square.
set of all palindromes made up of 0's and 1's
strings of 0's whose length is a prime number
string of odd number of zeroes

Question 10 of 70

10. Question

Which of the following pairs of regular expressions are equivalent?

1(01)* and (10)*1
x(xx)* and (xx)*x
(ab)* and a*b*
x* and x*x*

Question 11 of 70

11. Question

pic the correct statements.
The logic of Pumping lemma is a good example of

the Pigeon-hole principle
the divide and conquer technique
recursion
iteration

Question 12 of 70

12. Question

The basic limitation of an FSM is that

it can't remember arbitrary large amount of information
it sometimes recognize grammars that are not regular
it sometimes fails to recognize grammars that are regular
all of the above

Question 13 of 70

13. Question

Palindromes can’t be recognized by any FSM because

an FSM can't remember arbitrarily large amount of information
an FSM can't deterministically fix the mid-point
even if the mid-point is known an FSM can't find whether the second half of the string matches the first half
none of the above

Question 14 of 70

14. Question

An FSM can be considered TM

of finite tape length, rewinding capability and unidirectional tape movement
of finite tape length, without rewinding capability and unidirectional tape movement
of finite tape length, without rewinding capability and bidirectional tape movement
of finite tape length, rewinding capability and bidirectional tape movement

Question 15 of 70

15. Question

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 the above

Question 16 of 70

16. Question

The FSM pictured in Fig. 6.1 recognizes

all strings
no string
ε - alone
none of the above

Question 17 of 70

17. Question

The FSM pictured in Fiq. 6.2 is a

Mealy machine
Moore machine
Kleene machine
none of the above

Question 18 of 70

18. Question

The above machine

complements a given bit pattern
generates all strings of 0's and 1's
adds 1 to a given bit pattern
none of the above

Question 19 of 70

19. Question

The language of all words (made up of a’s and b’s) with at least two a’s can be described by the regular expression

(a+b)*a(a+b)*a(a+b)*
(a+b)*ab*a(a+b)*
b*ab*a(a+b)*
a(a+b)*a(a+b)*(a+b)*

Question 20 of 70

20. Question

Which of the following pairs of regular expression are not equivalent?

(ab)*a and a(ba)*
(a+b)* and (a*+b)*
(a*+b)* and (a+b)*
none of the above

Question 21 of 70

21. Question

Consider the two FSM’s in Fig 6.3.
Pick the correct statement.

Both are equivalent
The second FSM accept only ε
The first FSM accepts nothing
None of the above

Question 22 of 70

22. Question

Set of regular languages over a given alphabet set, is not closed under

union
complementation
intersection
none of the above

Question 23 of 70

23. Question

The machine pictured in Fig. 6.4.

complements a given bit pattern
finds 2's complement of a given bit pattern
increments a given bit pattern by 1
changes the sign bit

Question 24 of 70

24. Question

For which of the following application regular expressions can’t be used?

Designing compilers
Developing text editors
Simulating sequential circuits
Designing computers

Question 25 of 70

25. Question

The FSM pictured in Fig. 6.5 recognizes

any string of odd number of a's
any string of odd number of a's and even number of b's
any string of even number of a's and even number of b's
any string of even number of a's and odd number of b's

Question 26 of 70

26. Question

Any given Transition graph has an equivalent

regular expression
DFSM
NDFSM
none of the above

Question 27 of 70

27. Question

The following CFG
s→ as | bs | a | b
is equivalent to the regular expression

(a*+b)*
(a+b)*
(a+b) (a+b)*
(a+b)*(a+b)

Question 28 of 70

28. Question

Any string of terminals that can be generated by the following CFG
S → XY
X → aX | bX | a
Y → Ya | Yb | a

has at least one b
should end in an 'a'
has no consecutive a's or b's
has at least two a's

Question 29 of 70

29. Question

equal number of a's and b's
odd number of a's and odd number b's
ever number of a's and even number of b's
odd number a's and even number of a's

Question 30 of 70

30. Question

LET L(G) denote the language generated by the grammar G. TO prove set A = L (G),

it is enough to prove that an arbitrary member of A can be generated by grammar G
it is enough to prove that an arbitrary string generated by G, belongs to set A
both the above comments (a) and (b) are top be proved
either of the above comments (a) or (b) is to be proved

Question 31 of 70

31. Question

The set {aⁿbⁿ |n = 1,2,3…} can be generated by the CFG

S → ab | aSb
S → aaSbb | ab
S → ab | aSb | ε
S → aaSbb | ab | aabb

Question 32 of 70

32. Question

Choose the correct statements.

All languages can be generated by CFG.
Any regular language has an equivalent CFG.
Some non-regular language can't be generated by any CFG.
SO=ome regular languages can't be generated by any CFG.

Question 33 of 70

33. Question

Which of the following CFG’s can’t be simulated by an FSM?

S → Sa | a
S → abx X → cY Y → d| ax
S → aSb| ab
None of the above

Question 34 of 70

34. Question

CFG is not closed under

union
Kaleene star
complementation
product

Question 35 of 70

35. Question

The set A= {aⁿbⁿa^{n | n= 1, 2, 3, . . . ) is an example of a grammar that is}

regular
context free
not context free
none of the above

Question 36 of 70

36. Question

Let L1 = {aⁿbⁿa^m | m, n = 1, 2, 3 . . . }

L2 = ( aⁿb^ma^m| m, n = 1, 2, 3, . . . }

L3 = { aⁿbⁿaⁿ| n = 1, 2, 3, . . . . }

Choose the correct statements.

L3 = L1 n L2
L1 and L2 are CFL but L3 is not a CFL
L1 and L2 are not CFL but L3 is a CFL
L1 is a subset of L3

Question 37 of 70

37. Question

L = { aⁿbⁿaⁿ| n = 1, 2, 3, . . . . } is an exampble of a language that is

Context free
not context free
not context free but whose complement is CF
context free but whose complement is not CF

Question 38 of 70

38. Question

The intersection of a CFL and a regular language

need not be regular
need not context free
is always regular
is always CF

Question 39 of 70

39. Question

A PDM behaves like an FSM when the number of auxiliary memory it has is

0
1
2
none of the above

Question 40 of 70

40. Question

A PDM behave like a TM when the number of auxiliary memory it has is

0
1 or more
2 or more
none of the above

Question 41 of 70

41. Question

Choose the correct statements.

The power of DFSM and NDFSM are the same.
The power of DFSM and NDFSM are the different
The power of DPDM and NDPDM are the differet.
The power of DPDM and NDPDM are the same.

Question 42 of 70

42. Question

Which of the following is accepted by an NDPDM, but not by a DPDM?

All strings in which a given symbol is present at least twice.
Even palindromes (i.e palindromes made up of even number of terminals).
Strings ending with a particular terminal.
None of the above

Question 43 of 70

43. Question

CSG can be recognized by a

FSM
DPDM
NDPDM
linearly bounded memory machine

Question 44 of 70

44. Question

Choose the correct statemetns.

An FSM with 1 stack is more powerful than a FSM with no stack.
An FSM with 2 stack is more powerful than a FSM with 1 stack.
An FSM with 3 stack is more powerful than a FSM with 2 stack.
All of these

Question 45 of 70

45. Question

Choose the correct statements

An FSM with 2 stacks is as powerful as a TM.
DFSM and NDFSM have the same power.
A DFSM with 1 stack and an NDFSM with 1 stack have the same power.
A DFSM with 2 stacks and an NDFSM with 2 stacks have the same power.

Question 46 of 70

46. Question

Bounded minimization is a technique for

proving whether a primitive recursive function is Turning computable
proving whether a primitive recursive function is a total function
generating primitive recursive functions
generating partial recursive function

Question 47 of 70

47. Question

Which of the following is not primitive recursive but computable?

Carnot function
Rieman function
Bounded function
Ackermann function

Question 48 of 70

48. Question

Which of the following is not primitive recursive but partially recursive?

Carnot function
Rieman funcion
Bounded funtion
Ackermann function

Question 49 of 70

49. Question

Choose the correct statements.

A total recursive function is also a partial recursive function.
A partial recursive function is also a total recursive function.
A partial recursive function is also a primitive recursive function.
A primitive recursive function is also a partial recursive function.

Question 50 of 70

50. Question

A language L for which there exist a TM, T, that accepts every word in L and either rejects or loops for every word that is not in L, is said to be

recursive
recursively enumerable
NP-HARD
none of the above

Question 51 of 70

51. Question

Choose the correct statements.

L = { aⁿbⁿaⁿ| n = 1, 2, 3, . . . . } is recursively enumerable.
Recursive languages are closed under union.
Every recursive language is recursively enumerable.
Recursive languages are closed under intersection.

Question 52 of 70

52. Question

Choose the correct statements.

Set of recursively enumerable languages is closed under union.
If a language and its complement are both regular, then the language must be recursive.
Recursive languages are closed under complementation.
None of the above

Question 53 of 70

53. Question

Pick the correct answers.
Universal TM influenced the concept of

stored-program computers
interpretive implementation of programming languages.
computability
none of the above

Question 54 of 70

54. Question

The number of internal states of a UTM should be at least

1
2
3
4

Question 55 of 70

55. Question

The number of symbols necessary to simulate a TM with m symbols and n states is

m + n
8mn + 4m
mn
4mn + m

Question 56 of 70

56. Question

The statement – “A TM can’t solve halting problem” is

true
false
still an open question
none of the above

Question 57 of 70

57. Question

Any TM with m symbols and n states can be simulated by another TM with just 2 symbols and less than

8mn states
4mn + 8 states
8mn + 4 states
mn states

Question 58 of 70

58. Question

If there exists a TM which when applied to any problem in the class, terminates if the correct answer is yes, and may or may not terminate otherwise is said to be

stabel
unsolvable
partially solvable
unstable.

Question 59 of 70

59. Question

The number of stats of the FSM, required to simulate the behavior of a computer, with a memory capable of storing ‘m’ words, each of length ‘n’ bits it

m X 2ⁿ
2^mn
2^m+n
none of these

Question 60 of 70

60. Question

The vernacular language English, if considered a formal language, is a

regular language
context free language
context sensitive language
none of the above

Question 61 of 70

61. Question

Let P, Q and R be three languages. If P and R are regular and if PQ = R, then

Q has to be regular
Q cannot be regular
Q need not be regular
Q has to be a CFL

Question 62 of 70

62. Question

Consider the grammar
S → PQ | SQ | PS
P → X
Q → Y
To get a string of n terminals, the number of productions to be used is

n²
n + 1
2n
2n -1

Question 63 of 70

63. Question

Choose the correct statements.
A class of languages that is closed under

union and complemention has to be closed under intersection
intersection and complementation has to be closed under union
union and intersection has to be closed under complementation
all of the above

Question 64 of 70

64. Question

The following grammar is
S → aab | baac | aB

S → aS | b

S → abb | ab

ba → bdb | b

context free
regular
context sensitive
LR "(k)

Question 65 of 70

65. Question

Which of the following definitions generates the same language as L, where

L = {xⁿyⁿ, n ≥ 1} ?

I. E → xEy | xy

II. xy | x⁺xyy⁺

II. x⁺y⁺

I only
I and II
II and III
II only

Question 66 of 70

66. Question

A finite state machine with the following state table has a single input x and a single output z.
Present state | Next state, z
x=1 | X=0
A D,0 | B,0
B B,1 | C,1
C B,0 | D,1
D B,1 | c,0
If the initial state is unknown, then the shortest input sequence to reach the final state C is

01
10
101
110

Question 67 of 70

67. Question

Let A = {0,1} and L + A* Let R = {0ⁿ1ⁿ , n>0} The languages L U R and R are respectively

regular, regular
not regular, regular
regular, not regular
not regular, not regular

Question 68 of 70

68. Question

Which of the following conversion is not possible algorithmically?

Regular grammar to context free grammar
Non-deterministic FSA to deterministic FSA
Non-deterministic PDA to deterministic PDA
Non-deterministic Turing machine to deterministic Turing machine

Question 69 of 70

69. Question

An FSM can be used to add two given integers. This remark is

true
false
may be true
none of the above

Question 70 of 70

70. Question

A CFG is said to be in Chomsky Normal Form (CNF), if all the productions are of the form A → BC or A → a. Let G be a CFG in CNF. To derive a string of terminals of length x, the number of productions to be used is

2x - 1
2x
2x + 1
2^x