Bissoy.com
Doctors Medicines MCQs Q&A

Which of the following statements is/are TRUE? (a) The grammar S → SS | a is ambiguous. (Where S is the start symbol) (b) The grammar S → 0S1 | 01S |e is ambiguous. (The special symbol e represents the empty string) (Where S is the start symbol) (c) The grammar (Where S is the start symbol) S → T / U T → x S y | xy | ϵ U → yT generates a language consisting of the string yxxyy.

Which of the following statements is/are TRUE? (a) The grammar S → SS | a is ambiguous. (Where S is the start symbol) (b) The grammar S → 0S1 | 01S |e is ambiguous. (The special symbol e represents the empty string) (Where S is the start symbol) (c) The grammar (Where S is the start symbol) S → T / U T → x S y | xy | ϵ U → yT generates a language consisting of the string yxxyy. Correct Answer All of (a), (b) and (c) are TRUE.

The correct answer is option 4.

CONCEPT:

For grammar to be ambiguous, a string needs to have

More than one parse tree

More than two leftmost derivative

More than two rightmost derivative

Key Points

The grammar S → SS | a is ambiguous grammar. It generates two parse trees with string aaa. 

[ alt="F1 Raju Shraddha 07.04.2020 D10" src="//storage.googleapis.com/tb-img/production/21/04/F1_Raju_Shraddha_07.04.2020_D10.png" style="width: 216px; height: 177px;">

The grammar S → 0S1 | 01S |e is ambiguous. It generates two parse trees with string 01.

[ alt="F1 Raju Shraddha 07.04.2020 D11 1" src="//storage.googleapis.com/tb-img/production/21/04/F1_Raju_Shraddha_07.04.2020_D11_1.png" style="width: 217px; height: 123px;">

The grammar S → T / U, T → x S y | xy | ϵ, U → yT generates a language consisting of the string yxxyy.

[ alt="F1 Raju Shraddha 07.04.2020 D12 1" src="//storage.googleapis.com/tb-img/production/21/04/F1_Raju_Shraddha_07.04.2020_D12_1.png" style="width: 144px; height: 358px;">

∴ Hence the correct answer is All of (a), (b) and (c) are TRUE.

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)?  
The context free grammar S → SS | 0S1 | 1S0 | ɛ generates _________
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. 
Read the passage carefully and choose thebest answer to each question out of the four alternativesand click the button corresponding to it. To know language is to be able to speak it; even a childwho does not yet attend school can speak his or herlanguage. In order to speak a language it is important tolisten to it and to read a few pages in it everyday. A childpicks up language and learns to talk just as (s)he learnsto walk. Walking and talking comes naturally to a child asit grows. In our country, a child may grow up speakingmore than one language, if these languages are spoken inthe home and in the neighbourhood. we call this multilingualism. A child speaks a language or languagesmuch before (s)he starts going to school. To know alanguage then is first of all to be able to speak it as easilyand naturally as a tree year old child does. Later on thechild will learn to read and write in that language. In orderto read and write in a language, one has to speak it. But itis possible to speak a language but not able to read orwrite in it. A baby does not speak until it is nine monthsold but it understands a few words at six months of age.It has been listening ever since it was born, and even alittle before that. So the first strategy in speaking alanguage is to listen. It is necessary for one to __________ the language before(s)he writes in that language.
With reference to technologies for solar power production, consider the following statements: 1. 'Photovoltaics' is a technology that generates electricity by direct conversion of light into electricity, while 'Solar Thermal' is a technology that utilizes the Sun's rays to generate heat which is further used in the electricity generation process. 2. Photovoltaics generates Alternating Current (AC), while Solar Thermal generates Direct Current (DC). 3. India has a manufacturing base for Solar Thermal technology, but not for Photovoltaics. Which of the statements given above is/are correct?
Suppliers(Sid: integer, sname:string, city:string, street:string) Parts(pid:integer, pname:string, color:string) Catalog(sid:integer, pid:integer, cost:real) Consider the following relational query on the above database: SELECT S.sname FROM Suppliers S  WHERE S.sid NOT IN (SELECT C.sid FROM Catalog C WHERE C.pid NOT IN (SELECT P.pid FROM Parts P WHERE P.color < > ‘blue’)) Assume that relations corresponding to the above schema are not empty. Which of the following is the correct interpretation of the above query?
Which of the following statements are true and which of them are not true? a. A language without script is dialect. b. A language may have many dialects. c. Some languages do not have grammar. d. Sign language does not have a grammar.
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?
What is the output of the following JAVA program? class Test { public static void main (String [ ] args) { Test obj = new Test (); obj.start (); } void start () { String stra="do”; String strb = method (stra); System.out.print(“:” + stra + strb); } String method (String stra) { stra=stra+”good”; System.out.print (stra); return “good”; } }
Read the passage carefully and choose thebest answer to each question out of the four alternativesand click the button corresponding to it. To know language is to be able to speak it; even a childwho does not yet attend school can speak his or herlanguage. In order to speak a language it is important tolisten to it and to read a few pages in it everyday. A childpicks up language and learns to talk just as (s)he learnsto walk. Walking and talking comes naturally to a child asit grows. In our country, a child may grow up speakingmore than one language, if these languages are spoken inthe home and in the neighbourhood. we call thismultilingualism. A child speaks a language or languagesmuch before (s)he starts going to school. To know alanguage then is first of all to be able to speak it as easilyand naturally as a tree year old child does. Later on thechild will learn to read and write in that language. In orderto read and write in a language, one has to speak it. But itis possible to speak a language but not able to read orwrite in it. A baby does not speak until it is nine monthsold but it understands a few words at six months of age.It has been listening ever since it was born, and even alittle before that. So the first strategy in speaking alanguage is to listen. To know a language one must be able to?