Bissoy.com
Doctors Medicines MCQs Q&A

Identify the language generated by the following grammar, where S is the start variable. S → XY X → aX | a Y → aYb | ϵ

Identify the language generated by the following grammar, where S is the start variable. S → XY X → aX | a Y → aYb | ϵ Correct Answer {a<sup>m</sup>b<sup>n</sup> | m &gt; n, n ≥ 0}

Grammar:

S → XY

X → aX | a

Y → aYb | ϵ

Explanation:

X generates at least one a. Generates a string of type {a, aa, aaa, aaaa……}

ambn, if n = 0 and m = 0 ∴ string = ϵ which cannot be generated from the given grammar and hence option 2 is incorrect.

Y generates an equal number of a and b { ϵ, ab, aabb, ……} with a comes before b.

Since at least one a is generated by X and an equal number of a’s and b’s generated by Y ∴ m> n and hence option 1 is incorrect

The smallest length string generated by Y is ϵ. In ambn, n ≥ 0 and hence option 4 is incorrect.

{ a, aab, aaabb,………….} which is equivalent to :

L = {ambn | m > n, n ≥ 0}

Related Questions

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.
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 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 grammar G: P → Q + R | Q – R | Q | R Q → q | r R → r | s where P, Q, and R are non-terminal symbols, and q, r, and s are terminal symbols. Which of the following statement(s) is/are correct? S1. LL(1) can parse all strings that are generated using grammar G S2. LR(1) can parse all strings that are generated using grammar G
Consider the following grammar G S → F | H F → p | c H → d | c Where S, F, and H are non-terminal symbols, p, d, and c are terminal symbols. Which of the following statement(s) is/are correct? S1. LL(1) can parse all strings that are generated using grammar G S2. LR(1) can parse all string that are generated using grammar G
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?
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.
Consider the following context-free grammar over the alphabet ∑ = {a, b, c} with S as the start symbol: S → abScT | abcT T → bT | b Which one of the following represents the language generated by the above grammar?
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?
A teacher in her grammar class introduces the grammar item in a text and in single sentences and draws the attention of learners to its use through lots of examples and activities by learners. Once the learners are able to use the language item in context, she familiarizes the rules of the grammatical in order to internalize the form. What is this process of teaching-learning grammar known as?