Q.1
Consider the following statements about the context free grammarG = {S - >SS, S - >ab, S - >ba, S - ε}I. G is ambiguousII. G produces all strings with equal number of a’s and b’sIII. G can be accepted by a deterministic PDA.Which combination below expresses all the true statements about G?
  • 1 only
  • 1 and 3
  • 2 and 3
  • 1,2 and 3
Q.2
Consider the CFG with {S,A,B) as the non-terminal alphabet, {a,b) as the terminal alphabet, S as the start symbol and the following set of production rulesS --> aB S --> bAB --> b A --> aB --> bS A --> aSB --> aBB A --> bAAWhich of the following strings is generated by the grammar?
  • aaaabb
  • aabbbb
  • aabbab
  • abbbba
Q.3
Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?
  • Both DHAM3 and SHAM3 are NP-hard
  • SHAM3 is NP-hard, but DHAM3 is not
  • DHAM3 is NP-hard, but SHAM3 is not
  • Neither DHAM3 nor SHAM3 is NP-hard
Q.4
If L and L' are recursively enumerable, then L is
  • regular
  • context free
  • context sensitive
  • recursive
Q.5
For S € (0+1)* let d(s)denote the decimal value of s(e.g.d(101)= 5).Let L = {s € (0 +| d (s) mod 5 = 2 and d (s) mod 7 != 4)}Which one of the following statements is true?
  • L is recursively enumerable, but not recursive
  • L is recursive, but not context-free
  • L is context-free, but not regular
  • L is regular
Q.6
A minimum state deterministic finite automation accepting the language L = {W |W € {0,1}* , number of 0's and 1's in W are divisible by 3 and 5 respectively has
  • 15 States
  • 11 states
  • 10 states
  • 9 states
Q.7
Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least.
  • N^2
  • 2^N
  • 2N
  • N!
Q.8
If s is a string over (0 + 1)* then let n0 (s) denote the number of 0’s in s and n1 (s)the number of l’s in s. Which one of the following languages is not regular?
  • L = {s € (0 + 1)*n0 (s) is a 3-digit prime
  • L = {s € (0 + 1)* | for every prefix s’ of s, l 0 (s’) — n1 (s’) |
  • L={s € (0+1)* | n0(s) - n1(s) |
  • L = {s € (0 + 1) | n0 (s) mod 7 = n1 (s) mod 5 = 0 }
Q.9
Which of the following are decidable ?whether the intersection of two regular language is infinite.whether a give context free language is regularwhether two push down automata accept the same language.whether a given grammar is context free
  • 1 and 2
  • 1 and 4
  • 2 and 3
  • 2 and 4
Q.10
The language L = { 0^i 2 1 ^i i>-0 } over the alphabet (0,1,is
  • not recurcise
  • is recursive and deterministic CFL
  • is a regular language
  • is not a deterministic CFL but a CFL
0 h : 0 m : 1 s