Theory Of Computation Unit 1 Set 1

Computer Science Engineering (CSE),

Master of Computer Applications (MCA)

Practice Mode Previous Next
On This Page

This set of Theory of Computation Multiple Choice Questions & Answers (MCQs) focuses on Theory Of Computation Unit 1 Set 1

Q1 | The following grammarG = (N, T, P, S)N = {S, A, B}T = {a, b, c}P : S → aSaS → aAaA → bBB → bBB → c 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
Answer: is type 2 but not type 3
Q2 | The following grammarG = (N, T, P, S)N = {S, A, B, C, D, E}T = {a, b, c}P : S → aABAB → CDCD → CEC → aCC → bbE → 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
Answer: is type 1 but not type 2
Q3 | The following grammarG = (N, T, P, S)N = {S, A, B, C}T = {a, b, c}P : S → aSA → bBB → cCC → a 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
Answer: is type 3
Q4 | P, Q, R are three languages. If P & 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
Answer: Q need not be regular
Q5 | Which of the following is true with respect to Kleene’s theorem?1 A regular language is accepted by a finite automaton.2 Every language is accepted by a finite automaton or a turingmachine.
  • 1 only
  • 2 only
  • Both 1 and 2 are true statements
  • None is true
Answer: Both 1 and 2 are true statements
Q6 | Automaton accepting the regular expression of any number of a ' s is:
  • a*
  • ab*
  • (a/b)*
  • a*b*c
Answer: a*
Q7 | Grammars that can be translated to DFAs:
  • Left linear grammar
  • Right linear grammar
  • Generic grammar
  • All of these
Answer: Right linear grammar
Q8 | Two strings x and y are indistinguishable if:
  • δ*(s, x) = δ* (s, y), i.e. the state reached by a DFA M on input x is the same as the state reached by M on input y
  • if for every string z Є ∑* either both xz and yz are in language A on ∑* or both xz and yz are not in A
  • Both above statements are true
  • None of the above
Answer: Both above statements are true
Q9 | Given an arbitrary non-deterministic finite automaton NFA with N states, the maximum number of states in an equivalent minimized DFA is at least:
  • N2
  • 2N
  • N!
Answer: 2N
Q10 | Regular expressions are
  • Type 0 language
  • Type 1 language
  • Type 2 language
  • Type 3 language
Answer: Type 0 language
Q11 | The regular expression 0*(10)* denotes the same set as
  • (1*0)*1*
  • 0+(0+10)*
  • (0+1)*10(0+1)*
  • None of the above
Answer: 0+(0+10)*
Q12 | Consider the NFA M shown below. Let the language accepted by M be L. Let L1 be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true?
  • L1 = {0,1}* − L
  • L1 = {0,1}*
  • L1 is a subset of L
  • L1 = L
Answer: L1 = {0,1}* − L
Q13 | Which of the statements is true:
  • The complement of a regular language is always regular.
  • Homomorphism of a regular language is always regular.
  • Both of the above are true statements
  • None of the above
Answer: Both of the above are true statements
Q14 | The regular sets are closed under:
  • Union
  • Concatenation
  • Kleene closure
  • All of the above
Answer: All of the above
Q15 | Any given transition graph has an equivalent:
  • regular
  • DFSM (Deterministic Finite State Machine)
  • NDFSM
  • All of them
Answer: All of them
Q16 | A language is regular if and only if
  • Accepted by DFA
  • Accepted by PDA
  • Accepted by LBA
  • Accepted by Turing machine
Answer: Accepted by DFA
Q17 | Which of the following is not a regular expression?
  • [(a+b)*-(aa+bb)]*
  • [(0+1)-(0b+a1)*(a+b)]*
  • (01+11+10)*
  • (1+2+0)*(1+2)*
Answer: [(0+1)-(0b+a1)*(a+b)]*
Q18 | Consider the regular language L = (111+111111)*. The minimum number ofstates inany DFA accepting this language is
  • 3
  • 5
  • 8
  • 9
Answer: 9
Q19 | How many strings of length less than 4 contains the language described bythe regular expression (x+y)*y(a+ab)*?
  • 7
  • 10
  • 12
  • 11
Answer: 11
Q20 | Which of the following is TRUE?
  • Every subset of a regular set is regular
  • Every finite subset of a non-regular set is regular
  • The union of two non-regular sets is not regular
  • Infinite union of finite sets is regular
Answer: Every finite subset of a non-regular set is regular
Q21 | The minimum state automaton equivalent to the above FSA has the following number of states
  • 1
  • 2
  • 3
  • 4
Answer: 2
Q22 | Which one of the following languages over the alphabet {0,1} is describedby the regular expression: (0+1)*0(0+1)*0(0+1)*?
  • The set of all strings containing the substring 00.
  • The set of all strings containing at most two 0’s.
  • The set of all strings containing at least two 0’s.
  • The set of all strings that begin and end with either 0 or 1.
Answer: The set of all strings containing at least two 0’s.
Q23 | Let w be any string of length n is {0,1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?
  • n-1
  • n
  • n+1
  • 2n-1
Answer: n+1
Q24 | Which of the following are regular sets?
  • I and IV only
  • I and III only
  • I only
  • IV only
Answer: I and IV only
Q25 | A minimum state deterministic finite automation accepting the language L={W W ε {0,1}*, number of 0s and 1s in are divisible by 3 and 5, respectively} has
  • 15 states
  • 11 states
  • 10 states
  • 9 states
Answer: 15 states
Previous Next