Category: Automata Theory Objective Questions

Automata Theory Multiple Choice Questions on “Equivalence of One-Tape and Multitape TM’s”.

1. Which of the following are related to construction of One Tape turing machines?
a) JFLAP
b) NFLAP
c) Both (a) and (b)
d) None of the mentioned

Answer: a
Clarification: JFLAP is educational software written in java to experiment with the topics in automata theory and area of formal languages.

2. Which of the following topics cannot be covered using JFLAPS?
a) L-System
b) Unrestricted Grammar
c) Regular Expression
d) None of the mentioned

Answer: d
Clarification: Topics like regular expressions, context free languages and unrestricted grammar including parsers like LL,SLR parsers can be covered using JFLAPS.

3. State true or false:
Statement: Multitape turing machine have multi tapes where each tape is accessed with one head.
a) true
b) false

Answer: b
Clarification: Multitape turing machines do have multiple tapes but they they are accessed by separate heads.

4. Which of the following statements is/are true?
a) Every multitape turing machine has its equivalent single tape turing machine
b) Every multitape turing machine is an abstract machine
c) Both (a) and (b)
d) None of the mentioned

Answer: c
Clarification: A multitape turing machine is an ordinary turing machine which is always abstract.And they do have their equivalent single tape turing machines.

5. Are Multitape and Multitrack turing machines same?
a) Yes
b) No
c) Somewhat yes
d) Cannot tell

Answer: a
Clarification: Multitrack turing machines are special types of Multitape turing machines. In a standard n-tape Turing machine, n heads move independently along n-tracks.

6. In a n-track turing machine, _________ head/heads read and write on all tracks simultaneously.
a) one
b) two
c) n
d) infinite

Answer: a
Clarification: In a n-track Turing machine, one head reads and writes on all tracks simultaneously. A tape position in a n-track Turing Machine contains n symbols from the tape alphabet.

7. Which of the following does not exists?
a) Turing Machine with Multiple heads
b) Turing Machine with infinite tapes
c) Turing machine with two dimensional tapes
d) None of the mentioned

Answer: d
Clarification: All of the mentioned are one or the other kind of Turing machines in existence.

8. Can a multitape turing machine have an infinte number of tapes?
a) Yes
b) No

Answer: b
Clarification: One needs a finite number of tapes. The proofs that show the equivalence between multi-tape TM and one-band TM rely on the fact that the number of tapes is bounded.

9. Every language accepted by a k-tape TM is _____ by a single-tape TM.
a) accepted
b) not accepted
c) generated
d) not generated

Answer: a
Clarification: Its the theorem that states Every multitape turing machine can be simulated by a single tape turing machine and the corresponding language can be accepted.

10. Which of the following is/are a basic TM equivalent to?
a) Multitrack TM
b) Multitape TM
c) Non-deterministic TM
d) All of the mentioned

Answer: d
Clarification: Tms can be used as both: language recognizers/Computers. TMs are like universal computing machines with universal storage.

Automata Theory Interview Questions and Answers on “Deterministic Finite Automata-Introduction and Definition”.

1. Which of the following not an example Bounded Information?
a) fan switch outputs {on, off}
b) electricity meter reading
c) colour of the traffic light at the moment
d) none of the mentioned

Answer: b
Clarification: Bounded information refers to one whose output is limited and it cannot be said what were the recorded outputs previously until memorized.

2. A Language for which no DFA exist is a________
a) Regular Language
b) Non-Regular Language
c) May be Regular
d) Cannot be said

Answer: b
Clarification: A language for which there is no existence of a deterministic finite automata is always Non Regular and methods like Pumping Lemma can be used to prove the same.

3. A DFA cannot be represented in the following format
a) Transition graph
b) Transition Table
c) C code
d) None of the mentioned

Answer: d
Clarification: A DFA can be represented in the following formats: Transition Graph, Transition Table, Transition tree/forest/Any programming Language.

4. When are 2 finite states equivalent?
a) Same number of transitions
b) Same number of states
c) Same number of states as well as transitions
d) Both are final states

Answer: c
Clarification: Two states are said to be equivalent if and only if they have same number of states as well as transitions.

5. Can a DFA recognize a palindrome number?
a) Yes
b) No
c) Yes, with input alphabet as ∑*
d) Can’t be determined

Answer: b
Clarification: Language to accept a palindrome number or string will be non-regular and thus, its DFA cannot be obtained. Though, PDA is possible.

6. Which of the following is not an example of finite state machine system?
a) Control Mechanism of an elevator
b) Combinational Locks
c) Traffic Lights
d) Digital Watches

Answer: d
Clarification: Proper and sequential combination of events leads the machines to work in hand which includes The elevator, Combinational Locks, Traffic Lights, vending machine, etc. Other applications of Finite machine state system are Communication Protocol Design, Artificial Intelligence Research, A Turnstile, etc.

Automata Theory Quiz on “Building Regular Expressions”.

1. Which of the following is correct?
Statement 1: ε represents a single string in the set.
Statement 2: Ф represents the language that consist of no string.
a) Statement 1 and 2 both are correct
b) Statement 1 is false but 2 is correct
c) Statement 1 and 2 both are false
d) There is no difference between both the statements, ε and Ф are different notation for same reason

Answer: a
Clarification: ε represents a single string in the set namely, the empty string while Statement 2 is also correct.

2. The appropriate precedence order of operations over a Regular Language is
a) Kleene, Union, Concatenate
b) Kleene, Star, Union
c) Kleene, Dot, Union
d) Star, Union, Dot

Answer: c
Clarification: If a regular language expression is given, the appropriate order of precedence if the parenthesis is ignored is: Star or Kleene, Dot or Concatenation, Union or Plus.

3. Regular Expression R and the language it describes can be represented as:
a) R, R(L)
b) L(R), R(L)
c) R, L(R)
d) All of the mentioned

Answer: c
Clarification: When we wish to distinguish between a regular expression R and the language it represents; we write L(R) to be the language of R.

4. Let for ∑= {0,1} R= (∑∑∑) *, the language of R would be
a) {w | w is a string of odd length}
b) {w | w is a string of length multiple of 3}
c) {w | w is a string of length 3}
d) All of the mentioned

Answer: b
Clarification: This regular expression can be used to eliminate the answers and get the result. The length can be even and as well more than 3 when R= (∑∑∑) (∑∑∑) (particular case).

5. If ∑= {0,1}, then Ф* will result to:
a) ε
b) Ф
c) ∑
d) None of the mentioned

Answer: a
Clarification: The star operation brings together any number of strings from the language to get a string in the result. If the language is empty, the star operation can put together 0 strings, resulting only the empty string.

6. The given NFA represents which of the following NFA
a) (ab U a) *
b) (a*b* U a*)
c) (ab U a*)
d) (ab)* U a*

Answer: a
Clarification: The Regular expression (ab U a) * is converted to NFA in a sequence of stages as it can be clearly seen in the diagram. This NFA consist of 8 stated while its minimized form only contains 2 states.

7. Which of the following represents a language which has no pair of consecutive 1’s if ∑= {0,1}?
a) (0+10)*(1+ε)
b) (0+10)*(1+ε)*
c) (0+101)*(0+ε)
d) (1+010)*(1+ε)

Answer: a
Clarification: All the options except ‘a’ accept those strings which comprises minimum one pair of 1’s together.

8. The finite automata accept the following languages:
a) Context Free Languages
b) Context Sensitive Languages
c) Regular Languages
d) All the mentioned

Answer: c
Clarification: A finite automaton accepts the languages which are regular and for which a DFA can be constructed.

9. (a + b*c) most correctly represents:
a) (a +b) *c
b) (a)+((b)*.c)
c) (a + (b*)).c
d) a+ ((b*).c)

Answer: d
Clarification: Following the rules of precedence, Kleene or star operation would be done first, then concatenation and finally union or plus operation.

10. Which of the following regular expressions represents the set of strings which do not contain a substring ‘rt’ if ∑= {r, t}
a) (rt)*
b) (tr)*
c) (r*t*)
d) (t*r*)

Answer: d
Clarification: As Kleene operation is not on the whole of the substring, it will not repeat and maintain the order of t, r.

11. According to the precedence rules, x-y-z is equivalent to which of the following?
a) (x-y)-z
b) x-(y-z)
c) Both (x-y)-z and x-(y-z)
d) None of the mentioned

Answer: a
Clarification: In arithmetic, we group two of the same operators from the left, hence x-y-z is equivalent to (x-y)-z and not x-(y—z).

12. Dot operator in regular expression resembles which of the following?
a) Expressions are juxtaposed
b) Expressions are multiplied
c) Cross operation
d) None of the mentioned

Answer: a
Clarification: Dot operation or concatenation operation means that the two expressions are juxtaposed i.e. there are no intervening operators in between. In fact, UNIX regular expressions use the dot for an entirely different purpose: representing any ASCII character.

13. Which among the following is not an associative operation?
a) Union
b) Concatenation
c) Dot
d) None of the mentioned

Answer: d
Clarification: It does not matter in which order we group the expression with the operators as they are associative. If one gets a chance to group the expression, one should group them from left for convenience. For instance, 012 is grouped as (01)2.

14.Which among the following is equivalent to the given regular expression?
01*+1
a) (01)*+1
b) 0((1)*+1)
c) (0(1)*)+1
d) ((0*1)1*)*

Answer: c
Clarification: Using the rules of precedence on the give expression, c is the appropriate choice with the order of: Bracket>Kleene>Dot>Union

Automata Theory Multiple Choice Questions on “Context Free Grammar-Derivations and Definitions”.

1. The entity which generate Language is termed as:
a) Automata
b) Tokens
c) Grammar
d) Data

Answer: c
Clarification: The entity which accepts a language is termed as Automata while the one which generates it is called Grammar. Tokens are the smallest individual unit of a program.

2. Production Rule: aAb->agb belongs to which of the following category?
a) Regular Language
b) Context free Language
c) Context Sensitive Language
d) Recursively Ennumerable Language

Answer: c
Clarification: Context Sensitive Language or Type 1 or Linearly Bounded Non deterministic Language has the production rule where the production is context dependent i.e. aAb->agb.

3. Which of the following statement is false?
a) Context free language is the subset of context sensitive language
b) Regular language is the subset of context sensitive language
c) Recursively ennumerable language is the super set of regular language
d) Context sensitive language is a subset of context free language
Answer: d

4. The Grammar can be defined as: G=(V, ∑, p, S)
In the given definition, what does S represents?
a) Accepting State
b) Starting Variable
c) Sensitive Grammar
d) None of these

Answer: b
Clarification: G=(V, ∑, p, S), here V=Finite set of variables, ∑= set of terminals, p= finite productions, S= Starting Variable.

5. Which among the following cannot be accepted by a regular grammar?
a) L is a set of numbers divisible by 2
b) L is a set of binary complement
c) L is a set of string with odd number of 0
d) L is a set of 0ⁿ1ⁿ

Answer: d
Clarification: There exists no finite automata to accept the given language i.e. 0ⁿ1ⁿ. For other options, it is possible to make a dfa or nfa representing the language set.

6. Which of the expression is appropriate?
For production p: a->b where a∈V and b∈_______
a) V
b) S
c) (V+∑)*
d) V+ ∑

Answer: c
Clarification: According to the definition, the starting variable can produce another variable or any terminal or a variable which leads to terminal.

7. For S->0S1|e for ∑={0,1}*, which of the following is wrong for the language produced?
a) Non regular language
b) 0ⁿ1ⁿ | n>=0
c) 0ⁿ1ⁿ | n>=1
d) None of the mentioned

Answer: d
Clarification: L={e, 01, 0011, 000111, ……0ⁿ1ⁿ }. As epsilon is a part of the set, thus all the options are correct implying none of them to be wrong.

8. The minimum number of productions required to produce a language consisting of palindrome strings over ∑={a,b} is
a) 3
b) 7
c) 5
d) 6

Answer: c
Clarification: The grammar which produces a palindrome set can be written as:
S-> aSa | bSb | e | a | b
L={e, a, b, aba, abbbaabbba…..}

9. Which of the following statement is correct?
a) All Regular grammar are context free but not vice versa
b) All context free grammar are regular grammar but not vice versa
c) Regular grammar and context free grammar are the same entity
d) None of the mentioned

Answer: a
Clarification: Regular grammar is a subset of context free grammar and thus all regular grammars are context free.

10. Are ambiguous grammar context free?
a) Yes
b) No

Answer: a
Clarification: A context free grammar G is ambiguous if there is atleast one string in L(G) which has two or more distinct leftmost derivations.

Automata Theory Multiple Choice Questions on “DPDA and Ambiguous Grammars”.

1. CFGs are more powerful than:
a) DFA
b) NDFA
c) Mealy Machine
d) All of the mentioned

Answer: d
Clarification:
Context-free grammars are strictly more powerful than regular expressions:
1) Any language that can be generated using regular expressions can be generated by a context-free grammar.
2) There are languages that can be generated by a context-free grammar that cannot be generated by any regular expression.
As a corollary, CFGs are strictly more powerful than DFAs and NDFAs.

2. State true or false:
S-> 0S1|01
Statement: No regular expression exists for the given grammar.
a) true
b) false

Answer: a
Clarification: The grammar generates a language L such that L={0ⁿ1ⁿ|n>=1} which is not regular. Thus, no regular expression exists for the same.

3. For the given set of code, the grammar representing real numbers in Pascal has error in one of the six lines. Fetch the error.
(1) ->
(2) -> | epsilon
(3) -> | epsilon
(4) -> ‘E’ | epsilon
(5) -> + | – | epsilon
(6) -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
a) 3
b) 4
c) 2
d) No errors

Answer: a
Clarification:
–>
–> | epsilon
–> ‘.’ | epsilon
–> ‘E’ | epsilon
–> + | – | epsilon
–> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

4. Which among the following is incorrect with reference to a derivation tree?
a) Every vertex has a label which is a terminal or a variable.
b) The root has a label which can be a terminal.
c) The label of the internal vertex is a variable.
d) None of the mentioned

Answer: b
Clarification: The root or interms of the grammar, starting variable can not be a terminal.

5. Let G=(V, T, P, S)
where a production can be written as:
S->aAS|a
A->SbA|ba|SS
Which of the following string is produced by the grammar?
a) aabbaab
b) aabbaa
c) baabab
d) None of the mentioned

Answer: b
Clarification: The step wise grammar translation can be written as:
aAS->aSbaA->aabAS->aabbaa

6. Statement 1: Ambiguity is the property of grammar but not the language.
Statement 2: Same language can have more than one grammar.
Which of the following options are correct with respect to the given statements?
a) Statement 1 is true but statement 2 is false
b) Statement 1 is false but statement 2 is true
c) Both the statements are true
d) Both the statements are false

Answer: c
Clarification: One language can more than one grammar. Some can be ambiguous and some cannot.

7. Which of the following are non essential while simplifying a grammar?
a) Removal of useless symbols
b) Removal of unit productions
c) Removal of null production
d) None of the mentioned

Answer: d
Clarification: Here are some process used to simplify a CFG but to produce an equivalent grammar:
a) Removal of useless symbols(non terminal) b) Removal of Unit productions and c) Removal of Null productions.

8. Which of the following are context free language?
a) L={aⁱbⁱ|i>=0}
b) L={ww^r| w is a string and r represents reverse}
c) Both (a) and (b)
d) one of the mentioned

Answer: a
Clarification: None.

9. The language L ={aⁱ2bⁱ|i>=0} is:
a) recursive
b) deterministic CFL
c) regular
d) Two of the mentioned is correct

Answer: d
Clarification: The language is recursive and every recursive language is a CFL.

10. L->rLt|tLr|t|r
The given grammar produces a language which is:
a) All palindrome
b) All even palindromes
c) All odd palindromes
d) Strings with same begin and end symbols

Answer: c
Clarification: As there exists no production for the palindrome set, even palindromes like abba, aabbaa, baaaaaab, etc will not be generated.

Automata Theory Multiple Choice Questions on “Non Deterministic Turing Machines”.

1. X is a simple mathematical model of a computer. X has unrestricted and unlimited memory. X is a FA with R/W head. X can have an infinite tape divided into cells, each cell holding one symbol.
Name X?
a) Push Down Automata
b) Non deterministic Finite Automata
c) Turing machines
d) None of the mentioned

Answer: c
Clarification: Turing machine is known as universal computer. It is denoted by M=(Q,Σ,Ґ ,δ ,q0, B,F)

2. Which of the following is/are not an application of turing machine?
a) Language Recognization
b) Computers of functions on non negative numbers
c) Generating devices
d) None of the mentioned

Answer: d
Clarification: A turing machine can have many applications like : Enumerator (A turing machine with an output printer), function computer, etc.

3. State true or false:
Statement: Turing Machine can change symbols on its tape, whereas the FA cannot change symbols on tape.
a) true
b) false

Answer: a
Clarification: The following mentioned is the difference between 2-way FA and TM. Another instance is that TM has a read/write tape head while FA doesn’t.

4. Which of the following cannot be a possibility of a TM while it processes an input?
a) Enters accepting state
b) Enters non-accepting state
c) Enters infinite loop and never halts
d) None of the mentioned

Answer: d
Clarification: The following mentioned are the only possibilities of operating a string through a turing machine.

5. Pick the odd one out.
a) Subroutines
b) Multiple tracks
c) Shifting over
d) Recursion

Answer: d
Clarification: Except Recursion, all the other options are techniques of Turing Machine construction which further includes, Checking off symbols and Storage in finite control.

6. Which among the following is not true for 2-way infinte TM?
a) tape in both directions
b) Leftmost square not distinguished
c) Any computation that can be performed by 2-way infinite tape can also be performed by standard TM.
d) None of the mentioned

Answer: d
Clarification: All of the mentioned are correct statements for a two way infinite tape turing machine. Theorems say the power of such a machine is in no way superior than a standard turing machine.

7. Can a turing machine act like a transducer?
a) yes
b) no

Answer: a
Clarification: A turing machine can be used as a transducer. The most obvious way to do this is to treat the entire non blank portion of the initial tape as input, and to treat the entire blank portion of the tape when the machine halts as output.

8. Which of the following does not exists?
a) Mutitape TM
b) Multihead TM
c) Multidimentional TM
d) None of the mentioned

Answer: d
Clarification: If the tape contains k-dimentional array of cells infinte in all 2^k directions, for some fixed k and has a finite control, the machine can be called Multidimentional TM.

9. Enumerator is a turing machine with __________
a) an output printer
b) 5 input tapes
c) a stack
d) none of the mentioned

Answer: a
Clarification: Here, the turing machine can use the printer as an output device to print strings.
Note: There is no input to an enumerator. If it doesn’t halt, it may print an infinite set of strings.

10. For the following language, an enumerator will print:
L={aⁿbⁿ|n>=0}
a) aⁿbⁿ
b) {ab, a²b², a³b³, …}
c) {e, ab, a²b², a³b³, …}
d) None of the mentioned

Answer: b
Clarification: An enumerator is a turing machine with an output printer. It can use an printer as an output device to print output strings. As n also holds the value , epsilon will also be a part of the output set.

11. Complete the following statement:
Statement : A language is turing recognizable if an only if ___________
a) an enumerator enumerates it
b) it is finite
c) both (a) and (b)
d) none of the mentioned

Answer: a
Clarification: If an Enumerator E enumerates a language L, there is a turing machine M that recognizes language L. Also, If a turing machine M recognizes a language L, there is an enumerator for L.