Category: Automata Theory Objective Questions

Automata Theory Problems on “The Language of a Grammar, Inferences and Ambiguity”.

1. Which of the following is not a notion of Context free grammars?
a) Recursive Inference
b) Derivations
c) Sentential forms
d) All of the mentioned

Answer: d
Clarification: The following are the notions to express Context free grammars:
a) Recursive Inferences
b) Derivations
c) Sentential form
d) Parse trees

2. State true or false:
Statement: The recursive inference procedure determines that string w is in the language of the variable A, A being the starting variable.
a) true
b) false

Answer: a
Clarification: We apply the productions of CFG to infer that certain strings are in the language of a certain variable.

3. Which of the following is/are the suitable approaches for inferencing?
a) Recursive Inference
b) Derivations
c) Both Recursive Inference and Derivations
d) None of the mentioned

Answer: c
Clarification: Two inference approaches:
1. Recursive inference, using productions from body to head
2. Derivations, using productions from head to body

4. If w belongs to L(G), for some CFG, then w has a parse tree, which defines the syntactic structure of w. w could be:
a) program
b) SQL-query
c) XML document
d) All of the mentioned

Answer: d
Clarification: Parse trees are an alternative representation to derivations and recursive inferences. There can be several parse trees for the same string.

5. Is the following statement correct?
Statement: Recursive inference and derivation are equivalent.
a) Yes
b) No

Answer: a
Clarification: Yes, they are equivalent. Both the terminologies represent the two approaches of recursive inferencing.

6. A->aA| a| b
The number of steps to form aab:
a) 2
b) 3
c) 4
d) 5

Answer: b
Clarification: A->aA=>aaA=>aab

7. An expression is mentioned as follows. Figure out number of incorrect notations or symbols, such that a change in those could make the expression correct.
L(G)={w in T*|S→*w}
a) 0 Errors
b) 1 Error
c) 2 Error
d) Invalid Expression

Answer: a
Clarification: For the given expression, L(G)={w in T*|S→*w}, If G(V, T, P, S) is a CFG, the language of G, denoted by L(G), is the set of terminal strings that have derivations from the start symbol.

8. The language accepted by Push down Automaton:
a) Recursive Language
b) Context free language
c) Linearly Bounded language
d) All of the mentioned

Answer: b
Clarification: Push down automata accepts context free language.

9. Which among the following is the correct option for the given grammar?
G->X111|G1,X->X0|00
a) {0^a1^b|a=2,b=3}
b) {0^a1^b|a=1,b=5}
c) {0^a1^b|a=b}
d) More than one of the mentioned is correct

Answer: a
Clarification: Using the recursive approach, we can conclude that option a is the correct answer, and its not possible for a grammar to have more than one language.

10. Which of the following the given language belongs to?
L={a^mb^mc^m| m>=1}
a) Context free language
b) Regular language
c) Both (a) and (b)
d) None of the mentioned

Answer: d
Clarification: The given language is neither accepted by a finite automata or a push down automata. Thus, it is neither a context free language nor a regular language.

11. Choose the correct option:
Statement: There exists two inference approaches:
a) Recursive Inference
b) Derivation

a) true
b) partially true
c) false
d) none of the mentioned

Answer: a
Clarification: We apply the productions of a CFG to infer that certain strings are in a language of certain variable.

12. Choose the correct option:
Statement 1: Recursive Inference, using productions from head to body.
Statement 2: Derivations, using productions from body to head.
a) Statement 1 is true and Statement 2 is true
b) Statement 1 and Statement 2, both are false
c) Statement 1 is true and Statement 2 is false
d) Statement 2 is true and Statement 1 is true

Answer: b
Clarification: Both the statements are false. Recursive Inference, using productions from body to head. Derivations, using productions from head to body.

13. Which of the following statements are correct for a concept called inherent ambiguity in CFL?
a) Every CFG for L is ambiguous
b) Every CFG for L is unambiguous
c) Every CFG is also regular
d) None of the mentioned

Answer: a
Clarification: A CFL L is said to be inherently ambiguous if every CFG for L is ambiguous.

14. Which of the theorem defines the existence of Parikhs theorem?
a) Parikh’s theorem
b) Jacobi theorem
c) AF+BG theorem
d) None of the mentioned

Answer: a
Clarification: Rohit Parikh in 1961 proved in his MIT research paper that some context free language can only have ambiguous grammars.

Automata Theory Assessment Questions and Answers on “CFG-Eliminating Useless Symbols”.

1. Suppose A->xBz and B->y, then the simplified grammar would be:
a) A->xyz
b) A->xBz|xyz
c) A->xBz|B|y
d) none of the mentioned

Answer: a
Clarification: For the first step, substitute B in first production as it only produces terminal and remove B production as it has already been utilized.
We get A->xBz|xyz and now, as B has no production, we eliminate the terms which hold the variable B, thus the answer remain A->xyz.

2. Given Grammar: S->A, A->aA, A->e, B->bA
Which among the following productions are Useless productions?
a) S->A
b) A->aA
c) A->e
d) B->bA

Answer: d
Clarification: Some derivations are not reachable from the starting variable. As B is not reachable from the starting variable, it is a useless symbol and thus, can be eliminated.

3. Given:
S->…->xAy->…->w
if ____________, then A is useful, else useless symbol.
a) A is a non terminal
b) A is a terminal
c) w Î L
d) w Ë L

Answer: c
Clarification: Whatever operation we perform in intermediate stages, if the string produced belongs to the language, A is termed as useful and if not, not a useful variable.

4. Given:
S->aSb
S->e
S-> A
A->aA
B->C
C->D
The ratio of number of useless variables to number of useless production is:
a) 1
b) 3/4
c) 2/3
d) 0

Answer: a
Clarification: A, B, C, D are the useless symbols in the given grammar as they never tend to lead to a terminal. The productions S-> A, A->aA, B->C, C->D are also termed as useless production as they will never produce a string to the grammar.

5. Given grammar G:
S->aS|A|C
A->a
B->aa
C->aCb
Find the set of variables thet can produce strings only with the set of terminals.
a) {C}
b) {A,B}
c) {A,B,S}
d) None of the mentioned

Answer: c
Clarification: First step: Make a set of variables that directly end up with a terminal
Second step: Modify the set with variables that produce the elements of above
generated set.
The rest variables are termed as useless.

6. Given grammar:
S->aS|A
A->a
B->aa
Find the number of variables reachable from the Starting Variable?
a) 0
b) 1
c) 2
d) None of the mentioned
Answer: b

7. Inorder to simplify a context free grammar, we can skip the following operation:
a) Removal of null production
b) Removal of useless symbols
c) Removal of unit productions
d) None of the mentioned

Answer: d
Clarification: Inorder to simplify the grammar all of the process including the removal of null productions, unit productions and useless symbols is necessary.

8. Given a Grammar G:
S->aA
A->a
A->B
B->A
B->bb
Which among the following will be the simplified grammar?
a) S->aA|aB, A->a, B->bb
b) S->aA|aB, A->B, B->bb
c) S->aA|aB, A->a, B->A
d) None of the emntioned

Answer: a
Clarification: Step 1: Substitute A->B
Step 2: Remove B->B
Step 3: Substitute B->A
Step 4: Remove Repeated productions

9. Simplify the given grammar:
A-> a| aaA| abBc
B-> abba| b

a) A-> a| aaA| ababbAc| abbc
b) A-> a| aaA| ababbAc| abbc, B-> abba|b
c) A-> a| aaA| abbc, B->abba
d) None of the mentioned

Answer: a
Clarification: Using the substitution rules, we can simply eradicate what is useless and thus produce the simplified result i.e. A-> a| aaA| ababbAc| abbc.

10. In context to the process of removing useless symbols, which of the following is correct?
a) We remove the Nullable variables
b) We eliminate the unit productions
c) We eliminate products which yield no terminals
d) All of the mentioned

Answer: c
Clarification: In the process of removal of useless symbols, we want to remove productions that can never take part in any derivation.

Automata Theory Multiple Choice Questions on “Multistack Machines, Counter Machines”.

1. Can a single tape turing machine be simulated using deterministic 2-stack turing machine?
a) Yes
b) No
c) Cannot be said
d) none of the mentioned

Answer: a
Clarification: The symbols to left of the head of turing macine being simulated can be stored on the stack while the symbols on the right of the head can be placed on another stack. On each stack, symbols closer to the TM’s head are placed closer to the top of the stack than symbols farther from the TM’s head.

2. A ___________ is a multi tape turing machine whose input tape is read only.
a) Counter Machine
b) Multi-stack
c) Alternating Turing machine
d) None of the mentioned

Answer: a
Clarification: Counter machines are offline(a multitape turing machine whose input is read only) whose storage tapes are semi-infinite and whose tape symbols contains only two symbols Z and a blank symbol B.

3. Instantaneous description of a counter machine can be described using:
a) the input tape contents
b) position of the input head
c) distance of storage heads from symbol Z
d) all of the mentioned

Answer: d
Clarification: Instantaneous description of a counter machine can be described by the state, the input tape contents, the position of input head, and the distance of storage heads from the symbol Z. The counter machine can really store a count on each tape and tell if the count is zero.

4. Which of the following parameters cannot be used to restrict a turing machine?
a) tape alphabets
b) number of tapes
c) number of states
d) none of these

Answer: d
Clarification: Another procedure to restrict a turing machine is to limit the size of tape alphabet or reduce the number of states. If the tape alphabets, number of tapes or number of states are limited, then there is only a finite number of different turing machine, so the restricted model is more powerful than the original one.

5. Linear Bounded Automaton is a:
a) Finite Automaton
b) Turing Machine
c) Push down Automaton
d) None of the mentioned

Answer: b
Clarification: Linear Bounded Automaton is a type of Turing Machine where tape is not allowed to move off the portion of the tape containing the input. It is a Turing machine with limited amount of memory.

6. State true or false:
Statement: Using a two track tape, we can use a semi infinite tape to simulate an infinte tape.
a) true
b) false

Answer: true
Clarification: A TM with a semi-infinite tape means that there are no cells to the left of the initial head position. A TM with a semi infinite tape simulates a TM with an infinite tape by using a two-track tape.

7. Which of the following is true with reference to semi-infinite tape using a two track tape?
a) Can simulate a two way tape
b) Upper track represents the head-right cells
c) Lower track represents the head-left cells
d) All of the mentioned

Answer: d
Clarification: The upper track represents the cells of the original TM that are at the right of the initial head position. The lower track represents the cells to the left of the initial head position, but in reverse order.

8. Which among the following options are correct?
Statement 1: TMs can accept languages that are not accepted by any PDA with one stack.
Statement 2: But PDA with two stacks can accept any language that a TM can accept.
a) Statement 1 and 2, both are correct
b) Statement 1 is correct but Statement 2 is false
c) Statement 2 is correct while Statement 1 is false
d) Statement 1 and 2, both are false

Answer: a
Clarification: Both the statements are true. Both the statements are properties of Multistack machines.

9. A two-way infinite tape turing machine is ________ superior than the basic model of the turing machine in terms of power.
a) more
b) less
c) no way
d) none of the mentioned

Answer: c
Clarification: A two way infinite tape turing machine is a turing machine with its input tape infinte in both directions, the other component being the same as the basic model.

10. For a basic turing machine, there exists an equivalent :
a) 2-counter machine
b) 3-counter machine
c) 4-counter machine
d) All of the mentioned
Answer: d

Automata Theory Multiple Choice Questions on “The Language of DFA”

1. How many languages are over the alphabet R?
a) countably infinite
b) countably finite
c) uncountable finite
d) uncountable infinite

Answer: d
Clarification: A language over an alphabet R is a set of strings over A which is uncountable and infinite.

2. According to the 5-tuple representation i.e. FA= {Q, ∑, δ, q, F}
Statement 1: q ϵ Q’; Statement 2: FϵQ
a) Statement 1 is true, Statement 2 is false
b) Statement 1 is false, Statement 2 is true
c) Statement 1 is false, Statement 2 may be true
d) Statement 1 may be true, Statement 2 is false

Answer: b
Clarification: Q is the Finite set of states, whose elements i.e. the states constitute the finite automata.

3. δˆ tells us the best:
a) how the DFA S behaves on a word u
b) the state is the dumping state
c) the final state has been reached
d) Kleene operation is performed on the set

Answer: a
Clarification: δ or the Transition function describes the best, how a DFA behaves on a string where to transit next, which direction to take.

4. Which of the following option is correct?
A= {{abc, aaba}. {ε, a, bb}}
a) abcbb ₵ A
b) ε₵A
c) ε may not belong to A
d) abca ₵ A

Answer: b
Clarification: As the question has dot operation, ε will not be a part of the concatenated set. Had it been a union operation, ε would be a part of the operated set.

5. For a DFA accepting binary numbers whose decimal equivalent is divisible by 4, what are all the possible remainders?
a) 0
b) 0,2
c) 0,2,4
d) 0,1,2,3

Answer: d
Clarification: All the decimal numbers on division would lead to only 4 remainders i.e. 0,1,2,3 (Property of Decimal division).

6. The sum of minimum and maximum number of final states for a DFA n states is equal to:
a) n+1
b) n
c) n-1
d) n+2

Answer: a
Clarification: The maximum number of final states for a DFA can be total number of states itself and minimum would always be 1, as no DFA exits without a final state. Therefore, the solution is n+1.

7. Given:
L1= {xϵ ∑*|x contains even no’s of 0’s}
L2= {xϵ ∑*|x contains odd no’s of 1’s}
No of final states in Language L1 U L2?
a) 1
b) 2
c) 3
d) 4
Answer: c

8. The maximum number of transition which can be performed over a state in a DFA?
∑= {a, b, c}
a) 1
b) 2
c) 3
d) 4

Answer: c
Clarification: The maximum number of transitions which a DFA allows for a language is the number of elements the transitions constitute.

9. The maximum sum of in degree and out degree over a state in a DFA can be determined as:
∑= {a, b, c, d}
a) 4+4
b) 4+16
c) 4+0
d) depends on the Language

Answer: d
Clarification: The out degree for a DFA I fixed while the in degree depends on the number of states in the DFA and that cannot be determined without the dependence over the Language.

Automata Theory MCQs on “Conversion by Eliminating states”.

1. Which of the following is an utility of state elimination phenomenon?
a) DFA to NFA
b) NFA to DFA
c) DFA to Regular Expression
d) All of the mentioned

Answer: c
Clarification: We use this algorithm to simplify a finite automaton to regular expression or vice versa. We eliminate states while converting a given finite automata to its corresponding regular expression.

2. If we have more than one accepting states or an accepting state with an outdegree, which of the following actions will be taken?
a) addition of new state
b) removal of a state
c) make the newly added state as final
d) more than one option is correct

Answer: d
Clarification: If there is more than one accepting state or if the single accepting state as an out degree , add a new accepting state, make all other states non accepting, and hold an e-transitions from each former accepting state to the new accepting state.

3. Which of the following is not a step in elimination of states procedure?
a) Unifying all the final states into one using e-transitions
b) Unify single transitions to multi transitions that contains union of input
c) Remove states until there is only starting and accepting states
d) Get the resulting regular expression by direct calculation

Answer: b
Clarification: While eliminating the states, we unify multiple transitions to one transition that contains union of input and not the vice versa.

4. Is it possible to obtain more than one regular expression from a given DFA using the state elimination method?
a) Yes
b) No

Answer: a
Clarification: Using different sequence of removal of state, we can have different possible solution of regular expressions. For n-state deterministic finite automata excluding starting and final states, n! Removal sequences are there. It is very tough to try all the possible removal sequences for smaller expressions.

5. Which of the following methods is suitable for conversion of DFA to RE?
a) Brzozowski method
b) Arden’s method
c) Walter’s method
d) All of the mentioned

Answer: a
Clarification: Brzozowski method takes a unique approach to generating regular expressions. We create a system of regular expressions with one regular expression unknown for each state in M, and then we solve the system for Rλ where Rλ is the regular expression associated with starting state qλ.

6. State true or false:
Statement: The state removal approach identifies patterns within the graph and removes state, building up regular expressions along each transition.
a) true
b) false

Answer: a
Clarification: This method has the advantage over the transitive closure technique as it can easily be visualized.

7. The behaviour of NFA can be simulated using DFA.
a) always
b) never
c) sometimes
d) none of the mentioned

Answer: a
Clarification: For every NFA, there exists an equivalent DFA and vice versa.

8. It is suitable to use ____________ method/methods to convert a DFA to regular expression.
a) Transitive Closure properties
b) Brzozowski method
c) State elimination method
d) All of the mentioned

Answer: d
Clarification: For converting RE to DFA , first we convert RE to NFA (Thompson Construction), and then NFA is converted into DFA(Subset Construction).

9. State true or false:
Statement: For every removed state, there is a regular expression produced.
a) true
b) false

Answer: a
Clarification: For every state which is eliminated, a new regular expression is produced. The newly generated regular expression act as an input for a state which is next to removed state.

Automata Theory Multiple Choice Questions on “Sentential Forms”.

1. State true or false:
Statement: Every right-linear grammar generates a regular language.
a) True
b) False

Answer: a
Clarification: A CFG is said to right linear if each production body has at most one variable, and that variable is at the right end. That is, all productions of a right linear grammar are of the form A->wB or A->w, where A and B are variables while w is some terminal.

2. What the does the given CFG defines?
S->aSbS|bSaS|e and w denotes terminal
a) wwr
b) wSw
c) Equal number of a’s and b’s
d) None of the mentioned

Answer: c
Clarification: Using the derivation approach, we can conclude that the given grammar produces a language with a set of string which have equal number of a’s and b’s.

3. If L1 and L2 are context free languages, which of the following is context free?
a) L1*
b) L2UL1
c) L1.L2
d) All of the mentioned

Answer: d
Clarification: The following is a theorem which states the closure property of context free languages which includes Kleene operation, Union operation and Dot operation.

4. For the given Regular expression, the minimum number of variables including starting variable required to derive its grammar is:
(011+1)*(01)*
a) 4
b) 3
c) 5
d) 6

Answer: c
Clarification: The grammar can be written as:
S->BC
B->AB|ε
A->011|1
C->DC|ε
D->01

5. For the given Regular expression, the minimum number of terminals required to derive its grammar is:
(011+1)*(01)*
a) 4
b) 3
c) 5
d) 6

Answer: b
Clarification: The grammar can be written as:
S->BC
B->AB|ε
A->011|1
C->DC|ε
D->01

6. A grammar G=(V, T, P, S) is __________ if every production taken one of the two forms:
B->aC
B->a

a) Ambiguous
b) Regular
c) Non Regular
d) None of the mentioned

Answer: b
Clarification: The following format of grammar is of Regular grammar and is a part of Context free grammar i.e. like a specific form whose finite automata can be generated.

7. Which among the following is a CFG for the given Language:
L={x∈{0,1}*|number of zeroes in x=number of one’s in x}
a) S->e|0S1|1S0|SS
b) S->0B|1A|e A->0S B->1S
c) All of the mentioned

Answer: c
Clarification: We can build context free grammar through different approaches, recursively defining the variables and terminals inorder to fulfil the conditions.

8. Which of the following languages are most suitable for implement context free languages ?
a) C
b) Perl
c) Assembly Language
d) None of the mentioned

Answer: a
Clarification: The advantage of using high level programming language like C and Pascal is that they allow us to write statements that look more like English.

9. Which among the following is the correct grammar for the given language?
L={x∈{0,1}*|number of zeroes in x¹number of one’s in x}
a) S-> 0|SS|1SS|SS1|S1S
b) S-> 1|0S|0SS|SS0|S0S
c) S-> 0|0S|1SS|SS1|S1S
d) None of the mentioned

Answer: c
Clarification: L={0, 1, 00, 11, 001, 010,…}
The grammar can be framed as: S-> 0|0S|1SS|SS1|S1S

10. L={0ⁱ1^j2^k | j>i+k}
Which of the following satisfies the language?
a) 0111100
b) 011100
c) 0001100
d) 0101010

Answer: a
Clarification: It is just required to put the value in the variables in the question and check if it satisfies or not.