Theory of Compu...

Which one of the following is FALSE?

If L(G) is accepted by pushdown automaton and 'S' is a string of length 16 in L(G), how long is a derivative of x in G, if G is Chomsky normal form?

If L₁ and L₂ are context free language, then which of the following is always accepted by pushdown automaton (PDA)? 

Consider the languages L1, L2 and L3 as given below

L1 = {0^p1^q0^p | p, q ϵ N}

L2 = {0^p1^q | p, q ϵ N and p < q} and

L3 = {0^p1^q0^r | p, q, r ϵ N and p = q = r}

Which of the following statements is NOT TRUE?

If A is a deterministic context free language and B is also deterministic context language then which of the following will not be accepted by Deterministic Pushdown Automata?

I. A ∪ B

II. A̅ 

III. A ∩ B

IV. A U B̅ 

Consider the following languages:

L₁ = aⁿ b^3m c⁵ⁿ | n ≥ 1 and m ≥ 1

L₂ = a^2m b^p c²ⁿ d^q | m = n and p = q where m, n, p, q ≥ 0

L₃ = aⁿ b^p c^q  d^r | p = q = r where n, p, q, r ≥ 0

Which of the following is/are incorrect?

I. L₁ can be accepted by deterministic pushdown automaton.

II. L₂ can be accepted by the non-deterministic pushdown automaton

III. L₃ is a context-free language 

Which of the following is true over {0, 1}?

I. \(L_1={1^{50n}}\;|\;n \ge 1\)

II. \(L_2 ={ {2^{{n}}}\;|\;n \ge3}\) 

L₂ is written in the binary form where the given language is in decimal.