Multiple choice question for engineering
Set 1
1. CFGs are more powerful than:
a) DFA
b) NDFA
c) Mealy Machine
d) All of the mentioned
Answer
Answer: d [Reason:]
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
Answer: a [Reason:] The grammar generates a language L such that L={0n1n|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)
(3)
(4)
(5)
(6)
a) 3
b) 4
c) 2
d) No errors
Answer
Answer: a [Reason:]
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
Answer: b [Reason:] 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
Answer: b [Reason:] 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
Answer: c [Reason:] 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
Answer: d [Reason:] 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={aibi|i>=0}
b) L={wwr| w is a string and r represents reverse}
c) Both (a) and (b)
d) one of the mentioned
Answer
Answer: a
9. The language L ={ai2bi|i>=0} is:
a) recursive
b) deterministic CFL
c) regular
d) Two of the mentioned is correct
Answer
Answer: d [Reason:] 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
Answer: c [Reason:] As there exists no production for the palindrome set, even palindromes like abba, aabbaa, baaaaaab, etc will not be generated.
Set 2
1. Context free grammar is called Type 2 grammar because of ______________ hierarchy.
a) Greibach
b) Backus
c) Chomsky
d) None of the mentioned
Answer
Answer: c [Reason:] Chomsky hierarchy decide four type of language :Type 3- Regular Language, Type 2-Context free language, Type 1-Context Sensitive Language, Type 0- Unrestricted or Recursively Ennumerable language.
2. a→b
Restriction: Length of b must be atleast as much length of a.
Which of the following is correct for the given assertion?
a) Greibach Normal form
b) Context Sensitive Language
c) Chomsky Normal form
d) Recursively Ennumerable language
Answer
Answer: b [Reason:] A context-sensitive grammar (CSG) is a formal grammar in which the left-hand sides and right-hand sides of any production rules may be surrounded by a context of terminal and non terminal symbols. Context-sensitive grammars are more general than context-free grammars, in the sense that there are some languages that cannot be described by context-free grammars, but can be described by CSG.
3. From the definition of context free grammars,
G=(V, T, P, S)
What is the solution of VÇT?
a) Null
b) Not Null
c) Cannot be determined, depends on the language
d) None of the mentioned
Answer
Answer: a [Reason:] V is the set of non terminal symbols while T is the st of terminal symbols, their intersection would always be null.
4. If P is the production, for the given statement, state true or false.
P: V->(V∑T)* represents that the left hand side production rule has no right or left context.
a) true
b) false
Answer
Answer: a [Reason:] Here the production P is from the definition of Context free grammar and thus, has no right or left context.
5. There exists a Context free grammar such that:
X->aX
Which among the following is correct with respect to the given assertion?
a) Left Recursive Grammar
b) Right Recursive Grammar
c) Non Recursive Grammar
d) None of the mentioned
Answer
Answer: b [Reason:] The grammar with right recursive production is known as Right recursive grammar. Right recursive production is of the form X->aX where a is a terminal and X is a non terminal.
6. If the partial derivation tree contains the root as the starting variable, the form is known as:
a) Chomsky hierarchy
b) Sentential form
c) Root form
d) None of the mentioned
Answer
Answer: b [Reason:] Example: For any grammar, productions be:
S->AB
A->aaA| ^
B->Bb| ^
The partial derivation tree can be drawn as:
Since it has the root as S, this can be said to be in sentential form.
7. Find a regular expression for a grammar which generates a language which states :
L contains a set of strings starting wth an a and ending with a b, with something in the middle.
a) a(a*Ub*)b
b) a*(aUb)b*
c) a(a*b*)b
d) None of the mentioned
Answer
Answer: a [Reason:] The grammar for the same language can be stated as :
(1) S → aMb
(2) M → A
(3) M → B
(4) A → e
(5) A → aA
(6) B → e
(7) B → bB
8. Which of the following is the correct representation of grammar for the given regular expression?
a(aUb)*b
a) (1) S → aMb
(2) M → e
(3) M → aM
(4) M → bM
b) (1) S → aMb
(2) M → Mab
(3) M → aM
(4) M → bM
c) (1) S → aMb
(2) M → e
(3) M → aMb
(4) M → bMa
d) None of the mentioned
Answer
Answer: a [Reason:]
The basic idea of grammar formalisms is to capture the structure of string by
a) using special symbols to stand for substrings of a particular structure
b) using rules to specify how the substrings are combined to form new substrings.
9. A CFG consist of the following elements:
a) a set of terminal symbols
b) a set of non terminal symbols
c) a set of productions
d) all of the mentioned
Answer
Answer: d [Reason:] A CFG consists of:
a) a set of terminals, which are characters of alphabets that appear in the string generated by the grammar.
b) a set of non terminals, which are placeholders for patterns of terminal symbols that can be generated by the nonterminal symbols.
c) a set of productions, which are set of rules to transit from one state to other forming up the string
d) a start symbol, a special non terminal symbol that appears in the initial string generated in the grammar.
10. A CFG for a program describing strings of letters with the word “main” somewhere in the string:
a)
b)
c)
d) None of the mentioned
Answer
Answer: a [Reason:] None.
Set 3
1. The use of variable dependency graph is in:
a) Removal of useless variables
b) Removal of null productions
c) Removal of unit productions
d) None of the mentioned
Answer
Answer: a [Reason:] We use the concept of dependency graph inorder to check, whether any of the variable is reachable from the starting variable or not.
2. The variable which produces an epsilon is called:
a) empty variable
b) nullable
c) terminal
d) all of the mentioned
Answer
Answer: b [Reason:] Any variable A for which the derivation: A->*e is possible is called Nullable.
3. Statement:
For A-> e ,A can be erased. So whenever it appears on the left side of a production, replace with another production without the A.
State true or false:
a) true
b) false
Answer
Answer: b [Reason:] A can be erased. So whenever it appears on the right side of the production, replace with another production without the A.
4. Simplify the given grammar:
S->aXb
X->aXb | e
a) S->aXb | ab, X-> aXb | ab
b) S->X | ab, X-> aXb | ab
c) S->aXb | ab, X-> S | ab
d) None of the mentioned
Answer
Answer: a [Reason:] As X is nullable, we replace every right hand side presence of X with e and produce the simplified result.
5. Consider the following grammar:
A->e
B->aAbC
B->bAbA
A->bB
The number of productions added on the removal of the nullable in the given grammar:
a) 3
b) 4
c) 2
d) 0
Answer
Answer: b [Reason:] The modified grammar aftyer the removal of nullable can be shown as:
B->aAbC| abC
B->bAbA| bbA| bAb| bb
A->bB
6. Let G=(V, T, P, S) be a CFG such that _____________. Then there exists an equivalent grammar G’ having no e productions.
a) e ∈ L(G)
b) w ∉ L(G)
c) e ∉ L(G)
d) w ∈ L(G)
Answer
Answer: c [Reason:] Theorem: Let G = (V, T, S, P) be a CFG such that e ∉ L(G). Then there exists an equivalent grammar G’ having no e-productions.
7. For each production in P of the form:
A-> x1x2x3…xn
put into P’ that production as well as all those generated by replacing null variables with e in all possible combinations. If all x(i) are nullable,
a) A->e is put into P’
b) A->e is not put into P’
c) e is a member of G’
d) None of the mentioned
Answer
Answer: b [Reason:] It is an exception that A->e is not put into P’ if all x(i) are nullable variables.
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
Answer
Answer: d [Reason:] 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. Consider G=({S,A,B,E}, {a,b,c},P,S), where P consists of S →AB, A →a, B →b and E →c.
Number of productions in P’ after removal of useless symbols:
a) 4
b) 3
c) 2
d) 5
Answer
Answer: a [Reason:]
P’= S->AB, A->a, B-> b,
V’={S, A, B},
∑’={a, b}
10. Given grammar G:
S->aS| AB
A-> e
B-> e
D-> b
Reduce the grammar, removing all the e productions:
a) S->aS| AB| A| B, D-> b
b) S->aS| AB| A| B| a, D-> b
c) S->aS| AB| A| B
d) None of the mentioned
Answer
Answer: b [Reason:] We will replace all the nullables wherever they appear in the right hand side of any production. D will not be erased as we are just removing nullable variables not completely simplifying the grammar.
Set 4
1. Which among the following is the format of unit production?
a) A->B
b) A->b
c) B->Aa
d) None of the mentioned
Answer
Answer: a [Reason:] Any production of the format A-> B where A and B belongs to the V set, is called Unit production.
2. Given Grammar G:
S->aA
A->a| A
B->B
The number of productions to be removed immediately as Unit productions:
a) 0
b) 1
c) 2
d) 3
Answer
Answer: c [Reason:] The productions in the format A-> A are removed immediately as they produce self and that is not a terminal or will not lead to a string. Hence, it is removed immediately.
3. Given grammar:
S->aA
A->a
A->B
B-> A
B->bb
Which of the following is the production of B after simplification by removal of unit productions?
a) A
b) bb
c) aA
d) A| bb
Answer
Answer: b [Reason:] The simplified grammar can be presented as follows:
S->aA| aB
A->a
B-> bb
4. If grammar G is unambiguous, G’ produced after the removal of Unit production will be:
a) ambiguous
b) unambiguous
c) finite
d) cannot be said
Answer
Answer: b [Reason:] With the simplification of Context free grammars, undesirable properties are introduced. It says, if grammar G, before simplification is unambiguous, after simplification will also be unambiguous.
5. If C is A-derivable, C->B is a production, and B ¹ A, then B is
a) nullable
b) Non-derivable
c) A-derivable
d) None of the mentioned
Answer
Answer: c [Reason:]
If A-> B is a production, B is called A- derivable.
If C is A-derivable, C->B is a production, and B ¹ A, then B is A -derivable.
No other variables are A-derivable.
6. A can be A-> derivable if and only if __________
a) A-> A is actually a production
b) A->B, B-> A exists
c) Both (a) and (b)
d) None of the mentioned
Answer
Answer: a [Reason:] The format says: If A->B is a production, B is called A-derivable.Thus A to be A-derivable, a production : A-> A need to exist.
7. Given Grammar:
T-> T+R| R
R-> R*V| V
V->(T)| u
When unit productions are deleted we are left with
T-> T+R| _______|(T)| u
R->R*V|(T)| u
V-> (T)| u
Fill in the blank:
a) T*V
b) T+V
c) R*T
d) R*V
Answer
Answer: d [Reason:] The grammar produced after the elimination of unit production is:
T-> T+R| R*V| (T)| u
R->R*V|(T)| u
V-> (T)| u
8. Given grammar G:
S-> ABA, A->aA|e, B-> bB|e
Eliminate e and unit productions. State the number of productions the starting variable holds?
a) 6
b) 7
c) 9
d) 5
Answer
Answer: b [Reason:] After reduction the grammar looks like:
S->ABA| AB| BA| AA| Aa| a| bB| b
A->aA| a
B->bB| b
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
Answer
Answer: 5 [Reason:] 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. Which of the following variables in the given grammar is called live variable?
S->AB
A->a
a) S
b) A
c) B
d) None of the mentioned
Answer
Answer: b [Reason:] Any variable A for which there is a production A-> x with x Ε Σ* is called live.
Set 5
1. Which of the following does not belong to input alphabet if S={a, b}* for any language?
a) a
b) b
c) e
d) none of the mentioned
Answer
Answer: c [Reason:] The automaton may be allowed to change its state without reading the input symbol using epsilon but this does not mean that epsilon has become an input symbol. On the contrary, one assumes that the symbol epsilon does not belong to any alphabet.
2. The number of final states we need as per the given language?
Language L: {an| n is even or divisible by 3}
a) 1
b) 2
c) 3
d) 4
Answer
Answer: b [Reason:]
3. State true or false:
Statement: Both NFA and e-NFA recognize exactly the same languages.
a) true
b) false
Answer
Answer: a [Reason:] e-NFA do come up with a convenient feature but nothing new.They do not extend the class of languages that can be represented.
4. Design a NFA for the language:
L: {an| n is even or divisible by 3}
Which of the following methods can be used to simulate the same.
a) e-NFA
b) Power Construction Method
c) Both (a) and (b)
d) None of the mentioned
Answer
Answer: c [Reason:] It is more convenient to simulate a machine using e-NFA else the method of Power Construction is used from the union-closure of DFA’s.
5. Which of the following belongs to the epsilon closure set of a?
a) {f1, f2, f3}
b) {a, f1, f2, f3}
c) {f1, f2}
d) none of the mentioned
Answer
Answer: b [Reason:] The epsilon closure of the set q is the set that contains q, together with all the states which can be reached starting at q by following only epsilon transitions.
6. The number of elements present in the e-closure(f2) in the given diagram:
a) 0
b) 1
c) 2
d) 3
Answer
Answer: c [Reason:] The epsilon closure set of f2 consist of the elements:{f2, f3}. Thus the count of the element in the closure set is 2.
7. Which of the steps are non useful while eliminating the e-transitions for the given diagram?
a) Make a as accepting state of N’ if ECLOSE(p) contains an accepting state of N
b) Add an arc a to f1 labelled a if there is an arc labelled a in N from some state in ECLOSE(a) to f1
c) Delete all arcs labelled as e
d) None of the mentioned
Answer
Answer: d [Reason:] The given are the steps followed while eliminating epsilon transitions from a NFA or converting an e-NFA to just NFA.
8. Remove all the epsilon transitions in the given diagram and compute the number of a-transitions in the result?
a) 5
b) 7
c) 9
d) 6
Answer
Answer: b [Reason:]
Total Views: 18
