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?

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?

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?

If L and L' are recursively enumerable, then L is

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?

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

Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least.

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?

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

The language L = { 0^i 2 1 ^i i>-0 } over the alphabet (0,1,is