Question: Let G = (V, T, S, P) be the phrase-structure grammar with V = {0, 1, A, B, S}, T = {0, 1}, and set

Let G = (V, T, S, P) be the phrase-structure grammar with V = {0, 1, A, B, S}, T = {0, 1}, and set of productions P consisting of S → 0A, S → 1A, A → 0B, B → 1A, B → 1.
a) Show that 10101 belongs to the language generated by G.
b) Show that 10110 does not belong to the language generated by G.
c) What is the language generated by G?

Step by Step Solution

★★★★★

3.41 Rating (154 Votes )

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock

a It suffices to give a derivation of this string We write the derivation in the obvio... View full answer

Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock

Step: 3 Unlock

Document Format (1 attachment)

923-M-C-M-S (2657).docx

120 KBs Word File

Students Have Also Explored These Related Statistics Questions!

a) Construct a phrase-structure grammar that generates all signed decimal numbers, consisting of a sign, either + or ; a nonnegative integer; and a decimal fraction that is either the empty string or...

Use the set of productions to show that each of these sentences is a valid sentence. a) The happy hare runs b) The sleepy tortoise runs quickly c) The tortoise passes the hare d) The sleepy hare...

Find a phrase-structure grammar for each of these languages. a) The set consisting of the bit strings 0, 1, and 11 b) The set of bit strings containing only 1s c) The set of bit strings that start...

Let G = (V , T , S, P ) be the phrase-structure grammar with V = {0, 1, A, S}, T = {0, 1}, and set of productions P consisting of S ? 1S, S ? 00A, A ? 0A, and A ? 0. a) Show that 111000 belongs to...

Variation on 13.145] Let G = (V, T, S, P) be the phrase-structure grammar with V = {0, 1, A, B,S), T = { 0,1 }, and set of productions P consisting of S0A, S 1A, A 08, B 1A, B-1. 1. (a) Generate the...

Topic: Discrete Mathematics and its Applications(2012) Chapter 13 Modeling Computation "Languages and Grammars" Variation on 13.1#5] Let G = (V, T, S, P) be the phrase-structure grammar with V = {...

Let G = ( V , T , S , P ) be a phrase - structure grammar. Let w 0 = lz 0 r and w 1 = lz 1 r be strings over V . If z 0 - > z 1 is a production of G , we say that w 1 is from w 0 and we write w 0 w 1...

Let G = (V, T, S, P) be the phase-structure grammar with V = {0, 1, A, S}, T = {0, 1}, and P = {S rightarrow 1S, S rightarrow 00A, A rightarrow 0A, A rightarrow 0}. a. Show that 111000 belongs to the...

Let G = ( V , T , S , P ) be a context - free grammar such that every one of its productions is of the form A v , with | v | = k > 1 . Show that the derivation tree for any w in L ( G ) has a height...

Discrete Math Let G-(V, T, S, P) be the phrase-structure grammar with V= {0, 1, S. T3(0, 1), starting symbol S, and productions S--OS1 and S ?. Click and drag statements to show that G generates the...

Journalize the following transactions for Dukes of Hazzzzzzard, Inc. They are a boot retailer. They use PERPETUAL inventory. 9.5.14 9.10.14 9.15.14 Purchased $40,000 of boots on account from Laizy...

Boyne Painting Contractors needs to purchase a new truck. The owner is considering two different truck models that are currently on the market. Boynes two alternatives are presented below: Truck A:...

What are the three approaches or rules used by the courts when interpreting a statute? What is the so-called modern approach? What is the main objective of the court when it interprets a statute? In...

4. Which type of validity is especially important in an experiment?

(a) Sketch the curve y3 = x2. (b) Use Formulas 3 and 4 to set up two integrals for the arc length from (0, 0) to (1, 1). Observe that one of these is an improper integral and evaluate both of them....

Find the arc length function for the curve y = 2x3/2 with starting point P0 (1, 2).

(a) Graph the curve y = 1/3x3 + 1/(4x), x > 0. (b) Find the arc length function for this curve with starting point P0 (1, 1/12). (c) Graph the arc length function.

A poll found that 35% of adults do not work at all while on summer vacation. In a random sample of 5 adults, let x represent the number who do not work during summer vacation. Complete parts a...

The financial statement which summarizes operating, investing, and financing activities of an entity for a period of time is the a. retained earnings statement. b. income statement. c. statement of...

A marketing manager for a cell phone company claims that the percentage of children aged 8- 12 who have cell phones differs from 55%. In a survey of 880 children aged 8-12 by a national consumers...