Bissoy.com
Doctors Medicines MCQs Q&A

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?

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? Correct Answer S1 is correct and S2 is not correct

The proof of S1 can be seen in various book of theory of computation but s2 is a problem of category undecidable so a contradiction to this assumption can be easily obtained.

Related Questions

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?
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 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?
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 are TRUE? 1. The problem of determining whether there exists a cycle in an undirected graph is in P. 2. The problem of determining whether there exists a cycle in an undirected graph is in NP. 3. If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.
Which of the following statements are true of the teaching of grammar. A. Teaching of rules at the initial stage does not lend much to language learning. B. Rules of grammar are essential during the formative years of language learning. C. Grammar teaching should move from meaning to form. D. Grammar teaching should move from form to meaning. 
Consider the following statements. S1 : Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1). S2 : For any context-free grammar, there is a parser that takes at most O(n3) time to parse a string of length n. Which one of the following option is correct?
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
Read the passage given below and the two statements that follow (given on the basis of the passage): Four men are waiting at Delhi airport for a Mumbai flight. Two are doctors and the other two are businessmen. Two speak Gujarati and two speak Tamil, No two of the same profession, speak the same language. Two are Muslims and two are Christians. No two of the same religions are of the same profession, nor do they speak the same language, The Tamil-speaking doctor is a Christian. 1. The Christian-businessman speaks Gujarati. 2. The Gujarati-speaking doctor is a Muslim. Which of the above statements is/are correct conclusion/conclusions ?  
Which of the following statement(s) is/are FALSE? (i) Language L1 = {anbmcndm, n ≥ 0, m ≥ 0} is not context free grammar. (ii) Language L2 = {anbncn, n ≥ 0} is a context free grammar.