MCQ Computer Science

Automata Theory Multiple Choice Question & Answers (MCQs) set-7

1. If two sets, R and T has no elements in common i.e. RÇT=Æ, then the sets are called
a) Complement
b) Union
c) Disjoint
d) Connected

View Answer

Answer: c
Explanation: Two sets are called disjoint if they have no elements in common i.e. RÇT=Æ.

2. Which among the following is not a part of the Context free grammar tuple?
a) End symbol
b) Start symbol
c) Variable
d) Production

View Answer

Answer: a
Explanation: The tuple definition of context free grammar is: (V, T, P, S) where V=set of variables, T=set of terminals, P=production, S= Starting Variable.

3. A PDA machine configuration (p, w, y) can be correctly represented as:
a) (current state, unprocessed input, stack content)
b) (unprocessed input, stack content, current state)
c) (current state, stack content, unprocessed input)
d) none of the mentioned

View Answer

Answer: a
Explanation: A machine configuration is an element of K×S*×G*.
(p,w,?) = (current state, unprocessed input, stack content).

4. A language is accepted by a push down automata if it is:
a) regular
b) context free
c) both (a) and (b)
d) none of the mentioned

View Answer

Answer: c
Explanation: All the regular languages are the subset to context free languages and thus can be accepted using push down automata.

5. Which of the following is an incorrect regular expression identity?
a) R+f=R
b) eR=e
c) Rf=f
d) None of the mentioned

View Answer

Answer: b
Explanation: e is the identity for concatenation. Thus, eR=R.

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

View Answer

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

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

View Answer

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

8. For the given grammar G:
S->ABaC
A->BC
B->b| e
C->D| e
D-> d
Remove the e productions and generate the number of productions from S in the modified or simplified grammar.
a) 6
b) 7
c) 5
d) 8

View Answer

Answer: d
Explanation: The grammar after the removal of epsilon production can be shown as:
S->ABaC| AaC| ABa| Aa| a| aC| Ba| BaC
A->BC| B| C
B->b
C->D
D-> d
9. Given grammar G:
S-> A| B| C
A-> aAa| B
B-> bB|bb
C->aCaa|D
D->baD|abD|aa
Eliminate e and unit productions and state the number of variables left?
a) 5
b) 4
c) 3
d) 2

View Answer

Answer: 5
Explanation: The reduced production:
S->aAa| bB|bb aCaa| baD| abD| aa, A->aAa| bB| bb, B->bB| bb, C->aCaa| baD| abD| aa, D-> baD| abD| aa

10. Let G be a grammar: S->AB|e, A->a, B->b
Is the given grammar in CNF?
a) Yes
b) No

View Answer

Answer: a
Explanation: e is allowed in CNF only if the starting variable does not occur on the right hand side of the derivation.

11. The following format of grammatical notation is accepted by which of the following:
AB->CD
A->BC or
A->B or
A->a
where A, B, C, D are non terminal symbols and a is a terminal symbol.
a) Greibach Normal Form
b) Chomsky Nrmal Form
c) Kuroda Normal Form
d) None of the mentioned

View Answer

Answer: c
Explanation: Linearly Bounded grammar or Kuroda Normal Form allows the following format of grammatical analysis:
AB->CD
A->BC or
A->B or
A->a

12. Which among the following is a correct option in format for representing symbol and expression in Backus normal form?
a) <symbol> ->expression
b) <symbol>::=_expression_
c) <symbol>=<expression>
d) all of the mentioned

View Answer

Answer: b
Explanation: <symbol>::=_expression_ is the correct representation where <symbol> is a non terminal, and expression consist of one or more sequence of symbols, more sequence are separated by |, indicating a choice.
13. Which of the following is regular?
a) a100b100
b) (a+b)*-{a100b100}
c) Both (a) and (b)
d) None of the mentioned

View Answer

Answer: c
Explanation: As the language seems to be finite, a dfa can be constructed for the same, thus is regular.

14. A turing machine that is able to simulate other turing machines:
a) Nested Turing machines
b) Universal Turing machine
c) Counter machine
d) None of the mentioned

View Answer

Answer: b
Explanation: A more mathematically oriented definition with the same universal nature was introduced by church and turing together called the Church-Turing thesis(formal theory of computation).

15. If d is not defined on the current state and the current tape symbol, then the machine ______
a) does not halts
b) halts
c) goes into loop forever
d) none of the mentioned

View Answer

Answer: b
Explanation: If we reach hA or hR, we say TM halts. Once it has halted, it cannot move further, since d is not defined at any pair (hA,X) or (hR,X) where hA = accept halting state and hR = reject halting state.

Related Articles

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to top button