Theory Of Computation Unit 1 Set 2
On This Page
This set of Theory of Computation Multiple Choice Questions & Answers (MCQs) focuses on Theory Of Computation Unit 1 Set 2
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.