Consider the languages L1, L2 and L3 as given belowL1 = {0p1q

Turing machines can be used to recognize all the languages

Push Down Automata (PDA) can be used to recognize L1 and L2

All the three languages are context free

1.	Consider the languages L1, L2 and L3 as given belowL1 = {0p1q \| p, q ϵ N}L2 = {0p1q \| p, q ϵ N and p = q} andL3 = {0p1q0r \| p, q, r ϵ N and p = q r}Which of the following statements is NOT TRUE?
A.	Push Down Automata (PDA) can be used to recognize L1 and L2
B.	L1 is a regular language
C.	All the three languages are context free
D.	Turing machines can be used to recognize all the languages
Answer» D. Turing machines can be used to recognize all the languages

Discussion

No Comment Found

Related MCQs

For any two languages L1 and L2 such that L1 is context-free and L2 is recursively enumerable but not recursive, which of the following is/are necessarily true?I. L̅1 (complement of L1) is recursiveII. L̅2 (complement of L2) is recursiveIII. L̅1 is context-freeIV. L̅1 ∪ L2 is recursively enumerable
Consider the transition diagram of a PDA given below with input alphabet ∑ = {a, b} and stack alphabet Γ = {X, Z}. Z is the initial stack symbol. Let L denote the language accepted by the PDA.Which one of the following is TRUE?
Consider the NPDA 〈Q = {q0, q1, q2}, Σ = {0,1}, Γ = {0,1,⊥}, δ, q0, ⊥, F = {q2}〉, where (as per usual convention) Q is set of states, Σ is the input alphabet, Γ is the stack alphabet, δ is the state transition function, q0 is the initial state, ⊥ is the initial stack symbol, and F is the set of accepting states. The state transition is as follows:Which one of the following sequences must follow the string 101100 so that the overall string is accepted by the automaton?
If G is a grammar with productionsS → SaS | aSb | bSa | SS | ∈Where S is the start variable. Then which one of the following strings in not generated by G?
A student wrote two context-free grammars G1 and G2 for generating a single C-like array declaration. The dimension of the array is at least one. For example,int a[10] [3] ;The grammars use D as the start symbol, and use six terminal symbols int; id[ ] numGrammar G1Grammar G2D → int L;D → int L;L → id[EL → idEE → num]E → E[num]E → num][EE → [num] Which of the grammars correctly generate the declaration mentioned above?
Consider the following languages.L1 = {wxyx | w, x, y ϵ (0 + 1)+}L2 = {xy | x, y ϵ (a + b)*, |x| = |y|, x ≠ y}Which one of the following is TRUE?
Let L1 be a regular language and L2 be a context-free language. Which of the following languages is/are context-free?
A grammar that produces more than one left most derivation or right most derivation for the same sentence is known is _____.
Consider the following grammar.S → ABA → aA → BaBB → bbAWhich of the following statement is FALSE?
Consider the following languages :L1 = {am bn | m ≠ n}L2 = {am bn | m = 2n + 1}L3 = {am bn | m ≠ 2n}Which one of the following statement is correct ?

Consider the languages L1, L2 and L3 as given belowL1 = {0p1q | p, q ϵ N}L2 = {0p1q | p, q ϵ N and p = q} andL3 = {0p1q0r | p, q, r ϵ N and p = q r}Which of the following statements is NOT TRUE?

Discussion

No Comment Found

Related MCQs

Reply to Comment