Theory Of Computation Unit 1 Set 2 MCQs

Q1 | Let P be a regular language and Q be context-free language such that Q ∈ P. (For example, let P be the language represented by the regular expression p*q* and Q be {pnqnn∈ N}). Then which of the following is ALWAYS regular?

P ∩ Q

P – Q

∑* – P

∑* – Q

Q2 | Given a Non-deterministic Finite Automation (NFA) with states p and r as initial and final states respectively and transition table as given below:A BP - Qq R Sr R Ss R SThe minimum number of states required in Deterministic Finite Automation(DFA) equivalent to NFA is

5

4

3

2

Q3 | Which one of the following statement is true for a regular language L over {a} whose minimal finite state automation has two states?

L must be either {an I n is odd} or {an I n is even}

L must be {an I n is odd}

L must be {an I n is even}

L must be {an I n = 0}

Q4 | The …………. is said to be ambiguous if there exist at least one word of its language that can be generated by the different production tree .

CFL

CFG

GTG

None of the given

Q5 | Type-1 Grammar is known as_____________

CFG

CSG

REGULAR

All

Q6 | If G is “S → a S/a”, then L(G) = ?

a*

^

{a}+

Both (a) & (c)

Q7 | “S →a S”, what is the type of this production?

Type 0

Type 1

Type 2

Type 3

Q8 | A→abA a type __________productions

Type 0

Type 1

Type 2

Type 3

Q9 | The following CFG is inS → AB**spaceB → CD**spaceB → AD**spaceB → b**spaceD → AD**spaceD → d**spaceA → a**spaceC → a

Chomsky normal form but not strong Chomsky normal form

Weak Chomsky normal form but not Chomsky normal form

Strong Chomsky normal form

Greibach normal form

Q10 | The language accepted by a Push down Automata:

Type0

Type1

Type2

Type3

Q11 | Which of the following problems is undecidable?

Membership problem for CFGs

Ambiguity problem for CFGs

Finiteness problem for Finite state automata FSAs

Equivalence problem for FSAs

Q12 | Which one of the following statement is FALSE?

context-free languages are closed under union

context-free languages are closed under concatenation

context-free languages are closed under intersection

context-free languages are closed under Kleene closure

Q13 | Which of the following strings is not generated by the following grammar? S → SaSbSε

aabb

abab

aababb

aaabb

Q14 | Which of the following regular expression identity is true?

r(*) = r*

(r*s*)* = (r + s)*

(r + s)* = r* + s*

r*s* = r* + s*

Q15 | A language L is accepted by a FSA iff it is

CFL

CSL

Recursive

Regular

Q16 | Consider the following CFGS → aB S → bA**spaceB → b A → a**spaceB → bS A → aS**spaceB → aBB A → bAA**spaceConsider the following derivation**spaceS ⇒aB**space⇒aaBB**space⇒aaBb**space⇒aabSb**space⇒aabbAb**space⇒aabbab**spaceThis derivation is

A leftmost derivation

A rightmost derivation

Both leftmost and rightmost derivation

Neither leftmost nor rightmost derivation

Q17 | Consider the following language L = {anbncndnn ≥ 1} L is

CFL but not regular

CSL but not CFL

Regular

Type 0 language but not type 1

Q18 | A language is represented by a regular expression (a)*(a + ba). Which of the following strings does not belong to the regular set represented by the above expression?

aaa

aba

abab

aa

Q19 | Which of the following denotes Chomskianhiearchy?

REG ⊂ CFL ⊂ CSL ⊂ type0

CFL ⊂ REG ⊂ type0 ⊂ CSL

CSL ⊂ type0 ⊂ REG ⊂ CFL

CSL ⊂ CFL ⊂ REG ⊂ type0

Q20 | The concept of FSA is much used in this part of the compiler

Lexical analysis

Parser

Code generation

Code optimization

Q21 | The following grammarG = (N, T, P, S)**spaceN = {S, A, B, C, D, E}**spaceT = {a, b, c}**spaceP : S → aAB**spaceAB → CD**spaceCD → CE**spaceC → aC**spaceC → b**spacebE → bc is

is type 3

is type 2 but not type 3

is type 1 but not type 2

is type 0 but not type 1

Q22 | The following CFG is inS → aBB**spaceB → bAA**spaceA → a**spaceB → b

Chomsky normal form but not strong Chomsky normal form

Weak Chomsky normal form but not Chomsky normal form

Strong Chomsky normal form

Greibach normal form

Q23 | Which of the following statements is wrong?

The regular sets are closed under intersection

The class of regular sets is closed under substitution

The class of regular sets is closed under homomorphism

Context Sensitive Grammar(CSG) can be recognized by Finite State Machine

Q24 | Context free grammar is not closed under

Product operation

Union

Complementation

kleene star

Q25 | Which of the following statement is wrong?

Any regular language can be generated by a context-free grammar

Some non-regular languages cannot be generated by any CFG

the intersection of a CFL and regular set is a CFL

All non-regular languages can be generated by CFGs.