Thoery of Computation

From the options given below, the pair having different expressive power is

Deterministic Push Down Automata (DPDA) and Non-deterministic Push Down Automata (NPDA)

Deterministic Finite Automata (DFA) and Non-deterministic Finite Automata(NFA)

Single tape turning machine and multi tape turning machine.

Deterministic single tape turning machine and Non-Deterministic single tape turning machine

Correct! Wrong!

The language which is generated by the grammar S-> aSa I bSb I a I b over the alphabet {a, b} is the set of

Strings that begin and end with the same symbol

All odd and even length palindromes

All odd length palindromes

All even length palindromes

Correct! Wrong!

For the language {ap I P is a prime}, the statement which hold true is

It is not regular but context free

It is regular but not context free

It is neither regular nor context free, but accepted by a turing machine

It is not accepted by turing machine

Correct! Wrong!

The language described by the regular expression (0+1)0(0+1)0(0+1)* over the alphabet {0 1} is the set of

All strings containing at least two 1’s

All strings containing at least two 0’s

All strings that begin and end with either 0’s or 1’s

All strings containing the substring 00

Correct! Wrong!

Consider a stack, which is limited to 10 items. The language accepted by a push- down automaton in such stack is best described as

Regular

Deterministic context free

Context free

Recursive

Correct! Wrong!

Which one of the following statement is true if L denotes the language generated by the grammar S->0S0/00?

L is not context free

L is regular but not 0+

L = 0+

L is context free but not regular

Correct! Wrong!

We have two statements S1 and S2 whose definition are as follows: S1 – {02n In ≥ I} is a regular language. S2 – {0m 1n 0 1m+n Im=1 and n≥1I is a regular language. Which one of the following statements is correct?

Both S1 and S2 are correct

Only S2 is correct

Only S1 is correct

Neither S1 nor S2 is correct

Correct! Wrong!

S -> a α b I b a c I ab S -> α S I b S -> α bb I ab S -> bdb I b The grammar described above is

Context free

Context sensitive

Regular

D. LR(k)

Correct! Wrong!

Which one of the following is applicable for context free languages?

These are closed under union, Kleene closure

These are closed under complement, Kleene closure

These are closed under union, intersection

These are closed under intersection, complement

Correct! Wrong!

Which one of the following is true regarding FOTRAN?

It is a context free language

It is a context sensitive language

It is a regular language

None of the above

Correct! Wrong!

Let S and T be language over ={a,b} represented by the regular expressions (a+b) and (a+b)*, respectively. Which of the following is true?

ScT (S is a subset of T)

TcS (T is a subset of S)

S=T

SnT=Ø

Correct! Wrong!

Which of the following statements in true?

If a language is context free it can always be accepted by a deterministic push-down automaton

The union of two context free languages is context free

The intersection of two context free languages is context free

The complement of a context free language is context free

Correct! Wrong!

If L is DFA-regular, L’ is

Non regular

DFA-regular

Non-finite

None of the mentioned

Correct! Wrong!

Which of the following options is incorrect?

A language L is regular if and only if ~L has finite number of equivalent classes.

Let L be a regular language. If ~L has k equivalent classes, then any DFA that recognizes L must have atmost k states.

A language L is NFA-regular if and only if it is DFA-regular.

None of the mentioned

Correct! Wrong!

All the regular languages can have one or more of the following descriptions: i) DFA ii) NFA iii) e-NFA iv) Regular Expressions Which of the following are correct?

i, ii, iv

i, ii, iii

i, iv

i, ii, iii, iv

Correct! Wrong!

The major difference between a moore and mealy machine is that

output of the former depends on the present state and present input

output of the former depends only on the present state

output of former depends only on the present input

all of these

Correct! Wrong!

For which of the following application, regular expressions cannot be used ?

Designing computers

Designing compilers

Both (a) and (b)

Developing computers

Correct! Wrong!

If S be an infinite set and be sets such that S1 ∪ S2 ∪ .....∪ Sn = S, then

A. atleast one of the set Si is a finite set

B. not more than one of the sets Si can be finite

C. atleast one of the sets Si is an infinite set

not more than one of the sets Si can be infinite

Correct! Wrong!

If ∑ = {a, b, c, d, e, f } then number of strings in ∑ of length 4 such that no symbol is used more than once in a string is

35

360

49

720

Correct! Wrong!

An automation is a device and a grammar is a device.

generative, cognitive

generative, acceptor

acceptor, cognitive

cognitive, generative

Correct! Wrong!

From the options given below, the pair having different expressive power is

The language which is generated by the grammar S-> aSa I bSb I a I b over the alphabet {a, b} is the set of

For the language {ap I P is a prime}, the statement which hold true is

The language described by the regular expression (0+1)*0(0+1)*0(0+1)* over the alphabet {0 1} is the set of

Consider a stack, which is limited to 10 items. The language accepted by a push- down automaton in such stack is best described as

Which one of the following statement is true if L denotes the language generated by the grammar S->0S0/00?

We have two statements S1 and S2 whose definition are as follows: S1 – {02n In ≥ I} is a regular language. S2 – {0m 1n 0 1m+n Im=1 and n≥1I is a regular language. Which one of the following statements is correct?

S -> a α b I b a c I ab S -> α S I b S -> α bb I ab S -> bdb I b The grammar described above is

Which one of the following is applicable for context free languages?

Which one of the following is true regarding FOTRAN?

Let S and T be language over ={a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?

Which of the following statements in true?

If L is DFA-regular, L’ is

Which of the following options is incorrect?

All the regular languages can have one or more of the following descriptions: i) DFA ii) NFA iii) e-NFA iv) Regular Expressions Which of the following are correct?

The major difference between a moore and mealy machine is that

For which of the following application, regular expressions cannot be used ?

If S be an infinite set and be sets such that S1 ∪ S2 ∪ .....∪ Sn = S, then

If ∑ = {a, b, c, d, e, f } then number of strings in ∑ of length 4 such that no symbol is used more than once in a string is

An automation is a __________ device and a grammar is a __________ device.

Leave a Reply Cancel reply

The language described by the regular expression (0+1)0(0+1)0(0+1)* over the alphabet {0 1} is the set of

Let S and T be language over ={a,b} represented by the regular expressions (a+b) and (a+b)*, respectively. Which of the following is true?

An automation is a device and a grammar is a device.