Bissoy.com
Doctors Medicines MCQs Q&A

Consider the following problems. L(?) denotes the language generated by a grammar ?. L(?) denotes the language accepted by a machine ?. (I) For an unrestricted grammar ? and a string ?, whether ? ∈ (?) (II) Given a Turing machine M, whether L(M) is regular (III) Given two grammars ?1 and ?2, whether (?1) = (?2) (IV) Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language. Which one of the following statements is correct?

Consider the following problems. L(?) denotes the language generated by a grammar ?. L(?) denotes the language accepted by a machine ?. (I) For an unrestricted grammar ? and a string ?, whether ? ∈ (?) (II) Given a Turing machine M, whether L(M) is regular (III) Given two grammars ?1 and ?2, whether (?1) = (?2) (IV) Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language. Which one of the following statements is correct? Correct Answer Only I, II and III are undecidable

Membership algorithm does not exist for unrestricted grammars.

Regularity problem for TM is undecidable.

Equivalence of Two grammar is undecidable.

Every NFA is a PDA with a finite memory.

Related Questions

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)?  
Which of the following statements is/are FALSE? 1. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine. 2. Turing recognizable languages are closed under union and complementation. 3. Turing decidable languages are closed under intersection and complementation. 4. Turing recognizable languages are closed under union and intersection.
Which of the following problems are decidable? I. Checking whether two regular languages are equivalent languages II. Checking whether two non-deterministic finite automata accept the same language III. Checking whether two context free grammars generate equivalent languages  IV. Checking whether a language of a context free grammar is non-empty
Which among the following options are correct? Statement 1: TMs can accept languages that are not accepted by any PDA with one stack. Statement 2: But PDA with two stacks can accept any language that a TM can accept.
Consider the following two statements: I. If all states of an NFA are accepting states then the language accepted by the NFA is ∑*. II. There exists a regular language A such that for all languages B, A ∩ B is regular. Which one of the following is CORRECT?
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[ ] num Grammar G1 Grammar G2 D → int L; D → int L; L → id[E L → idE E → num] E → E[num] E → num][E E → [num]   Which of the grammars correctly generate the declaration mentioned above?
Consider the following statements. I. The complement of every Turing decidable language is Turing decidable II. There exists some language which is in NP but is not Turing decidable III. If L is a language in NP, L is Turing decidable Which of the above statements is/are true?
A signal is said to be 1. Deterministic if there is no uncertainty over the signal at any instant of time. 2. Deterministic if it is expressible through a mathematical equation. 3. Random or non-deterministic if there is uncertainty over the signal at the instant of time. 4. Random or non-deterministic if it is not expressible through a mathematical equation. Which of the above statements are correct?
Which of the following statement(s) is/are TRUE? (i) For every NFA with an arbitrary number of final states, there is an equivalent NFA with only one final state. (ii) A language that is accepted by a DFA will also be accepted by some NFA.
Without needing extra __________ we can simulate non deterministic turing machine using deterministic turing machine.