Theory Of Computation Unit 1 Set 1
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
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
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
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
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
Q6 | Automaton accepting the regular expression of any number of a ' s is:
- a*
- ab*
- (a/b)*
- a*b*c
Q7 | Grammars that can be translated to DFAs:
- Left linear grammar
- Right linear grammar
- Generic grammar
- All of these
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
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!
Q10 | Regular expressions are
- Type 0 language
- Type 1 language
- Type 2 language
- Type 3 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
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
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
Q14 | The regular sets are closed under:
- Union
- Concatenation
- Kleene closure
- All of the above
Q15 | Any given transition graph has an equivalent:
- regular
- DFSM (Deterministic Finite State Machine)
- NDFSM
- 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
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)*
Q18 | Consider the regular language L = (111+111111)*. The minimum number ofstates inany DFA accepting this language is
- 3
- 5
- 8
- 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
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
Q21 | The minimum state automaton equivalent to the above FSA has the following number of states
- 1
- 2
- 3
- 4
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.
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
Q24 | Which of the following are regular sets?
- I and IV only
- I and III only
- I only
- 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