Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M. Which of the following decision problems are undecidable?I. Given a regular expression R and a string w, is w ∈ L(R)?II. Given a context-free grammar G, is L(G) = ϕ?III. Given a context-free grammar G, is L(G) = ∑* for some alphabet ∑?IV. Given a Turing machine M and a string w, is w ∈ L(M)?

Let L(R) be the language represented by regular expression R. Let L(G)

1.	Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M. Which of the following decision problems are undecidable?I. Given a regular expression R and a string w, is w ∈ L(R)?II. Given a context-free grammar G, is L(G) = ϕ?III. Given a context-free grammar G, is L(G) = ∑* for some alphabet ∑?IV. Given a Turing machine M and a string w, is w ∈ L(M)?
A.	I and IV only
B.	II and III only
C.	II, III and IV only
D.	III and IV only
Answer» E.

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 ?

Discussion

No Comment Found

Related MCQs

Reply to Comment