Q2.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 : Option AExplaination / Solution:
Options B and C will accept the string b
Option – D will accept the string “bba”
Both are invalid strings.
So the minimized DFA is option A
Q4.Which one of the following options is CORRECT given three positive integers x, y and z, and a predicate
P (x) = ¬ (x = 1) ∧ ∀y (∃z (x = y * z) ⇒ (y = x) ∨ (y = 1))
Answer : Option AExplaination / Solution: No Explaination.
2) If L is context-free language, then, is also context-free?
3) If L is regular language, then, is also regular?
4) If L is recursive language, then, is also recursive?
Answer : Option DExplaination / Solution:
CFL’s are not closed under complementation. Regular and recursive languages are closed
under complementation.
Q6.Given the language L-{ab, aa, baa}, which of the following strings are in L*?
1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab
4) baaaaabaa
Answer : Option CExplaination / Solution:
L ={ab, aa, baa}
Let S1 = ab , S2 = aa and S3 =baa
abaabaaabaa can be written as S1S2S3S1S2
aaaabaaaa can be written as S1S1S3S1
baaaaabaa can be written as S3S2S1S2
Q8.What is the correct translation of the following statement into mathematical logic?
“Some real numbers are rational”
Answer : Option CExplaination / Solution:
Option A: There exists x which is either real or rational and can be both.
Option B: All real numbers are rational
Option C: There exists a real number which is rational.
Option D: There exists some number which is not rational or which is real.
Q9.For the grammar below, a partial LL(1) parsing table is also presented along with the
grammar. Entries that need to be filled are indicated as E1, E2, and E3. ε is the empty
string, $ indicates end of input, and | separates alternate right hand sides of productions.
S → a AbB| bAa B| ε
A → S
B → S
The First and Follow sets for the non-terminals A and B are
Q10.For the grammar below, a partial LL(1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2, and E3. ε is the empty string, $ indicates end of input, and | separates alternate right hand sides of productions.
S → a AbB| bAa B| ε
A → S
B → S
The appropriate entries for E1, E2, and E3 are
Answer : Option CExplaination / Solution:
Total Question/Mark :
Scored Mark :
Mark for Correct Answer : 1
Mark for Wrong Answer : -0.5
Mark for Left Answer : 0