1. Which of the following pairs have different expressive power?
a) DFA AND NDFA
b) DPDA AND NPDA
c) Deterministic single tape turing machine and Non-Deterministic single tape turing machine
d) single tape turing machine and multiple tape turing machine
ANSWER IS B
DPDA cannot handle languages or grammars with ambiguity, but NDPDA can handle languages with ambiguity and any context-free grammar.
2. The lexical analysis for a modern computer language such as java needs the power of which one of the following models in a necessary and sufficient sense?
a) Finite state automata
b) Deterministic pushdown automata
c) Non-deterministic pushdown automata
d) Turing machine
ANSWER IS A
3. which of the following problem is undecidable?
a) Membership problem of CFG
B) Ambiguity problem for CFG
c) Finiteness problem for FSA
d) Equivalence problem for FSA
ANSWER IS B
4. The recognizing capability of NDFSM and DFSM
a) is different b) sometimes different
c) is the same d) none of these
ANSWER IS C
5. FSM can recognize
a) any grammer b) only CFG
c) any unambiguous grammer d) only regular grammer
ANSWER IS D
6. Pumping lemma is generally used for proving
a) a given grammer is regular
b) a given grammer is not regular
c) weather two given regular expressions are not equivalent
d) none of above
ANSWER IS B
7. Which of following are not regular?
a) Strings of 0’s whose length is a perfect square
b) Set of all palindromes made up of 0’s and 1’s
c) String of 0’s, whose length is a prime number
d) String of odd numbers of zeros
ANSWER IS A,B,C
8. Which of the following pairs of regular expression are equivalent?
a) 1 (01) * and (10)*1 b) x (xx)* and (xx)*x
c) (ab)* and a*b* d) x^+ and x*x^+
ANSWER IS A,B,D
9. Assuming P!=NP, which of time is TRUE?
a) NP-complete=NP b) NP-complete intersection P= Ø
c) NP-hard=NP d) P=NP-complete
ANSWER IS B
10. The lexical analysis for a modern language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?
(A) Finite state automata
(B) Deterministic pushdown automata
(C) Non-deterministic pushdown automata
(D) Turing machine
Answer (A)
Lexical analysis is the first step in compilation. In lexical analysis, program is divided into tokens. Lexical analyzers are typically based on finite state automata. Tokens can typically be expressed as different regular expressions:
An identifier is given by [a-zA-Z][a-zA-Z0-9]*
The keyword if is given by if.
Integers are given by [+-]?[0-9]+.
11. A deterministic finite automation (DFA)D with alphabet ∑= {a,b} is given below
Which of the following finite state machines is a valid minimal DFA which accepts the same language as D?
Answer (A)
Options (B) and (C) are invalid because they both accept ‘b’ as a string which is not accepted by give DFA. D is invalid because it accepts bb+a which are not accepted by given DFA.
12. Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true? (GATE CS 2000)
(a) L = O
(b) L is regular but not O
(c) L is context free but not regular
(d) L is not context free
Answer: (b)
Explanation: Please note that grammar itself is not regular but language L is regular as L can be represented using a regular grammar, for example S -> S00/00.
References:
http://en.wikipedia.org/wiki/Regular_grammar
13. Consider the following two statements:
S1: { 0^2n |n >= l} is a regu1ar language
S2: { 0^m 0^n 0^(m+n) l m >= 1 and n >= 2} is a regu1ar language
Which of the following statements is correct? (GATE CS 2001)
a) Only S1 is correct
b) Only S2 is correct
c) Both S1 and S2 are correct
d) None of S1 and S2 is correct
Answer: (c)
Explanation:
S1 can be written as (00)^n where n >= 1. And S2 can be written as (00)^(m+n) where m >=2 and n >= 1. S2 can be further reduced to (00)^x where x >= 3.
We can easily write regular grammars for both S1 and S2.
G1 -> G100/00 (For S1)
G2 -> G200/000000 (For S2)
14. Which of the following statements in true? (GATE CS 2001)
(a) If a language is context free it can always be accepted by a deterministic push-down automaton
(b) The union of two context free languages is context free
(c) The intersection of two context free languages is context free
(d) The complement of a context free language is context free
Answer: (b)
Explanation:
Context-free languages are closed under the following operations. That is, if L and P are context-free languages and D is a regular language, the following languages are context-free as well:
• the Kleene star L * of L
• the image Ø(L) of L under a homomorphism Ø
• the concatenation of L and P
• the union of L and P
• the intersection of L with a regular language D (L n D).
Context-free languages are not closed under complement, intersection, or difference.
Why a) is not true?
The language recognized by deterministic pushdown automaton is deterministic context free language. Not all context-free languages are deterministic. This is unlike the situation for deterministic finite automata, which are also a subset of the nondeterministic finite automata but can recognize the same class of languages (as demonstrated by the subset construction).
References:
http://en.wikipedia.org/wiki/Context-free_language
http://en.wikipedia.org/wiki/Deterministic_pushdown_automaton
15. Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least. (GATE CS 2001)
(a) N^2
(b) 2^N
(c) 2N
(d) N!
Answer: (b)
16.Let S and T be language over ={a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true? (GATE CS 2000)
(a) ScT (S is a subset of T)
(b) TcS (T is a subset of S)
(c) S=T
(d) SnT=Ø
Answer: (c).
17) What is the complement of the language accepted by the NFA shown below? Assume ∑ = {a} and ε is the empty string
(A) Φ
(B) ε
(C) a
(D) {a, ε}
Answer (B)
The given alphabet ∑ contains only one symbol {a} and the given NFA accepts all strings with any number of occurrences of ‘a’. In other words, the NFA accepts a+. Therefore complement of the language accepted by automata is empty string.
18 Given the language L = {ab, aa, baa}, whih of the following strings are in L*?
1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab
4) baaaaabaa
(A) 1, 2 and 3
(B) 2, 3 and 4
(C) 1, 2 and 4
(D) 1, 3 and 4
Answer (C)
Any combination of strings in set {ab, aa, baa} will be in L*.
….1) “abaabaaabaa” can be partitioned as a combination of strings in set {ab, aa, baa}. The partitions are “ab aa baa ab aa”
….2) “aaaabaaaa” can be partitioned as a combination of strings in set {ab, aa, baa}. The partitions are “aa ab aa aa”
….3) “baaaaabaaaab” cannot be partitioned as a combination of strings in set {ab, aa, baa}
….4) “baaaaabaa” can be partitioned as a combination of strings in set {ab, aa, baa}. The partitions are “baa aa ab aa”
19) Which of the following problems are decidable?
….1) Does a given program ever produce an output?
….2) If L is a context-free language, then is L’ (complement of L) also context-free?
….3) If L is a regular language, then is L’ also regular?
….4) If L is a recursive language, then, is L’ also recursive?
(A) 1, 2, 3, 4
(B) 1, 2,
(C) 2, 3, 4
(D) 3, 4
Answer (D)
….1) Is a variation of Turing Machine Halting problem and it is undecidable.
….2) Context Free Languages are not closed under intersection and complement. See thisfor details.
….3) Complement of Regular languages is also regular. Then a DFA that accepts the complement of L, i.e. ∑* – L, can be obtained by swapping its accepting states with its non-accepting states.
….4) Recursive Languages are closed under complement.
20. Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For examples, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below.
The missing arcs in the DFA are
Answer (D)
State ‘q’ is trap state. All other states are accept states. In state 00, DFA must move to ‘q’ for input symbol 0. All (non-trap) states indicate names indicate the characters seen before reaching that particular state. Option (D) is the only option that follow these rules.