Note: This Question is unanswered, help us to find answer for this one
2. We have two statements S1 and S2 whose definition are as follows: S1 – {02n In ≥ I} is a regular language. S2 – {0m 1n 0 1m+n Im=1 and n≥1I is a regular language. Which one of the following statements is correct?
Answer
Correct Answer:
Only S1 is correct
Note: This Question is unanswered, help us to find answer for this one
3. Which one of the following statement is true for the C language?
Answer
Correct Answer:
It is context-sensitive language
Note: This Question is unanswered, help us to find answer for this one
4. We have decision problems P1 and P2 as described below: P1: Does a given finite state machine accept a given string? P2: Does a given context-free grammar generate an infinite number of strings? The statement that holds true for P1 and P2 is:
Answer
Correct Answer:
Both P1 and P2 are decidable
Note: This Question is unanswered, help us to find answer for this one
5. The last two symbols of L which is the set of all binary strings are same. In the minimum state deterministic finite state automaton, which is accepting L _____, states are present.
Answer
Correct Answer:
5
Note: This Question is unanswered, help us to find answer for this one
6. Let n be the length of a character string. How many substrings (of all lengths inclusive) can be formed from n?
Answer
Correct Answer:
(n (n+1)/2) + 1
Note: This Question is unanswered, help us to find answer for this one
7. The problem that is undecidable:
Answer
Correct Answer:
Ambiguity problem for CFG’s
Note: This Question is unanswered, help us to find answer for this one
8. Which one of the following statement is true?
Answer
Correct Answer:
The union of two context free languages is context free
Note: This Question is unanswered, help us to find answer for this one
9. From the options given below, the pair having different expressive power is:
Answer
Correct Answer:
Deterministic Push Down Automata (DPDA) and Non-deterministic Push Down Automata (NPDA)
Note: This Question is unanswered, help us to find answer for this one
10. 3-SAT and 2-SAT problems are:
Answer
Correct Answer:
NP-complete and in P respectively
Note: This Question is unanswered, help us to find answer for this one
11. Which one of the following is true for this automaton?
Answer
Correct Answer:
B*a(a+b)*
Note: This Question is unanswered, help us to find answer for this one
12. Consider a string s over (0+1)*. The number of 0’s in s is denoted by no(s) and the number of 1’s in s is denoted by n1(s). The language that is not regular is:
Answer
Correct Answer:
L = {s ∈ (0+1)* I no(s)-n1(s) I ≤ 4
Note: This Question is unanswered, help us to find answer for this one
13. We have an undirected graph G(V, E) with two problems given below: α – Does G have an independent set of size IVI – 4? β – Does G have an independent set of size 5? The statement that holds true is:
Answer
Correct Answer:
α is in P and β is NP-complete
Note: This Question is unanswered, help us to find answer for this one
14. The set that can be recognized by a deterministic finite state automaton is:
Answer
Correct Answer:
1, 2, 4, 8……2n ….. written in binary
Note: This Question is unanswered, help us to find answer for this one
15. Consider the language L = {W I W ∈ {0, 1}*, where 0’s and 1’s in W are divisible by 3 and 5 respectively. The minimum state deterministic finite automaton accepting the language L has:
Answer
Correct Answer:
15 states
Note: This Question is unanswered, help us to find answer for this one
16. Out of the three decision problems P1, P2 and P3, P1 is decidable and P2 is undecidable. The statement that holds true is:
Answer
Correct Answer:
P3 is undecidable if P2 is reducible to P3
Note: This Question is unanswered, help us to find answer for this one
17. The true regular expression is:
Answer
Correct Answer:
(r*s*)* = (r+s)*
Note: This Question is unanswered, help us to find answer for this one
18. Which one of the following is applicable for context free languages?
Answer
Correct Answer:
These are closed under union, Kleene closure
Note: This Question is unanswered, help us to find answer for this one
19. The language described by the regular expression (0+1)*0(0+1)*0(0+1)* over the alphabet {0 1} is the set of:
Answer
Correct Answer:
All strings containing at least two 0’s
Note: This Question is unanswered, help us to find answer for this one
20. For the language {ap I P is a prime}, the statement which hold true is
Answer
Correct Answer:
It is neither regular nor context free, but accepted by a turing machine
Note: This Question is unanswered, help us to find answer for this one
