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
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
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
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
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
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
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
Explanation: Inorder to simplify the grammar all of the process including the removal of null productions, unit productions and useless symbols is necessary.
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
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
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
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
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
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
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.
a) a100b100
b) (a+b)*-{a100b100}
c) Both (a) and (b)
d) None of the mentioned
View Answer
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
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).
a) does not halts
b) halts
c) goes into loop forever
d) none of the mentioned
View Answer
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.
