Computer Science – Automata Theory

The word ‘formal’ in formal languages means

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

Choose the correct statements.

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

Choose the correct statements.

The recognizing capability of NDFSM and DFSM

FSM can recognize

Pumping lemma is generally used for proving

Which of the following are not regular?

Which of the following pairs of regular expressions are equivalent?

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

The basic limitation of an FSM is that

Palindromes can’t be recognized by any FSM because

An FSM can be considered TM

Tm is more powerful than FSM because

The FSM pictured in Fig. 6.1 recognizes

The FSM pictured in Fiq. 6.2 is a

The above machine

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

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

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

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

The machine pictured in Fig. 6.4.

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

The FSM pictured in Fig. 6.5 recognizes

Any given Transition graph has an equivalent

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

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

The following CFG
S → aB | bA
A → b | aS | bAA
B → b | bS | aBB
generates strings of terminals that have

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

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

Choose the correct statements.

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

CFG is not closed under

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

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.

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

The intersection of a CFL and a regular language

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

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

Choose the correct statements.

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

CSG can be recognized by a

Choose the correct statemetns.

Choose the correct statements

Bounded minimization is a technique for

Which of the following is not primitive recursive but computable?

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

Choose the correct statements.

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

Choose the correct statements.

Choose the correct statements.

Pick the correct answers.
Universal TM influenced the concept of

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

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

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

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

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

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

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

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

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

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

The following grammar is
S → aab | baac | aB

S → aS | b

S → abb | ab

ba → bdb | b

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⁺

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

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

Which of the following conversion is not possible algorithmically?

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

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