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

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

Only II

B

Only III

C

Only I and II

D

Only I and III

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?

A

Both G1 and G2

B

Only G1

C

Only G2

D

Neither G1 nor G2

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?

A

Only I and II are undecidable

B

Only III is undecidable

C

Only II and IV are undecidable

D

Only I, II and III are undecidable

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

A nondeterministic finite automation with ε-moves is an extension of nondeterministic finite automation.

A

True

B

False

Which of the following problems are decidable? 1) Does a given program ever produce an output? 2) If L is a context-free language, then, is L̅ also context-free? 3) If L is a regular language, then, is L̅ also regular? 4) If L is a recursive language, then, is L̅ also recursive?

A

1, 2, 3, 4

B

1, 2

C

2, 3, 4

D

3, 4

Assume the statements S1 and S2 given as: S1: Given a context free grammar, there exists an algorithm for determining whether L (G) is infinite. S2: There exists an algorithm to determine whether two context free grammars generate the same language. Which of the following is true?

A

S1 is correct and S2 is not correct

B

Both S1 and S2 are correct

C

Both S1 and S2 are not correct

D

S1 is not correct and S2 is correct

Which of following problems are undecidable? I. Membership problem in context-free languages II. Whether a given context-free language is regular III. Whether a finite state automation halts on all inputs IV. Membership problem for type 0 languages

A

I and IV

B

II and IV

C

III and IV

D

I and II

Let L1, L2 be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT? I. L1 ∪ L2 is context-free II. L̅1 is context-free III. L1 – R is context-free IV. L1 ∩ L2 is context-free

A

I, II and IV only

B

I and III only

C

II and IV only

D

I only

Which of the following statements about Regular Expression is/are incorrect? A. The union of two regular expressions is also a regular expression B. The concatenation of two regular expressions is also a regular expression C. The iteration of a regular expression is also a regular expression

A

Only C

B

Only A

C

Both A and C

D

A, B and C

Grammar	W∈L(G)	L(G)=ϕ	L(G)=∑ϕ	L(G1)⊆L(G2)	L(G1)=L(G2)	L(G1)∩L(G2)=ϕ	L(G) is regular?	L(G) is finite ?
Regular Grammar	D	D	D	D	D	D	D	D
Det. Context Free	D	D	D	UD	D	UD	D	D
Context Free	D	D	UD	UD	UD	UD	UD	D
Context Sensitive	D	UD	UD	UD	UD	UD	UD	UD
Recursive	D	UD	UD	UD	UD	UD	UD	UD
Recursively Enumerable	UD	UD	UD	UD	UD	UD	UD	UD

Related Questions