Question

In: Computer Science

Ex#3: Give a string of lengths, 4, 6, 8 generated by the following grammar G =...

Ex#3: Give a string of lengths, 4, 6, 8 generated by the following grammar G = (V, T, S. P).
S → 0S
S --> 0S1S
S --> λ

Solutions

Expert Solution

Answer:

String length	String
4	0000
6	000000
8	00000000

Explanation:

Given production rules.

S → 0S
S --> 0S1S
S --> λ

String derivation:

4 lenght string: 0000

Step1: S → 0S

Step2: substitute 0S in S, S → 00S , [Since S --> 0S]

Step3: substitute 0S in S, S → 000S , [Since S --> 0S]

Step4: substitute 0S in S, S → 0000S , [Since S --> 0S]

Step5: substitute λ in S, S → 0000 , [Since S --> λ, which is null string]

So we can derive 0000 as 4 length string from the given rules.

6 lenght string: 000000

Step1: S → 0S

Step2: substitute 0S in S, S → 00S , [Since S --> 0S]

Step3: substitute 0S in S, S → 000S , [Since S --> 0S]

Step4: substitute 0S in S, S → 0000S , [Since S --> 0S]

Step5: substitute 0S in S, S → 00000S , [Since S --> 0S]

Step6: substitute 0S in S, S → 000000S , [Since S --> 0S]

Step7: substitute λ in S, S → 000000 , [Since S --> λ, which is null string]

So we can derive 000000 as 6 length string from the given rules.

8 lenght string: 000000

Step1: S → 0S

Step2: substitute 0S in S, S → 00S , [Since S --> 0S]

Step3: substitute 0S in S, S → 000S , [Since S --> 0S]

Step4: substitute 0S in S, S → 0000S , [Since S --> 0S]

Step5: substitute 0S in S, S → 00000S , [Since S --> 0S]

Step6: substitute 0S in S, S → 000000S , [Since S --> 0S]

Step7: substitute 0S in S, S → 0000000S , [Since S --> 0S]

Step8: substitute 0S in S, S → 00000000S , [Since S --> 0S]

Step9: substitute λ in S, S → 00000000 , [Since S --> λ, which is null string]

So we can derive 00000000 as 8 length string from the given rules.

***Please give Upvote ***

venereology answered 1 year ago

Next > < Previous

Related Solutions

Consider the following. n = 8 measurements: 4, 3, 7, 8, 5, 6, 4, 6 Calculate...

Consider the following. n = 8 measurements: 4, 3, 7, 8, 5, 6, 4, 6 Calculate the sample variance, s2, using the definition formula. (Round your answer to four decimal places.) s2 = Calculate the sample variance, s2 using the computing formula. (Round your answer to four decimal places.) s2 = Find the sample standard deviation, s. (Round your answer to three decimal places.) s =

Using the same data… 2 3 4 4 4 6 6 6 7 8 8 9...

Using the same data… 2 3 4 4 4 6 6 6 7 8 8 9 10 10 11 12 16 16 28 46 (d) [5 pts] Determine the 5# summary. (e) Determine the lower and upper fence to determine if there are any outliers. (f) Draw and carefully label a modified boxplot for this data. (g) What is the shape of the distribution (symmetric, skewed left, or skewed right). Explain.

For the following data set, X: 9, 6, 8, 3, 8, 9, 3, 4, 3, 7:...

For the following data set, X: 9, 6, 8, 3, 8, 9, 3, 4, 3, 7: Calculate: 1. Variance 2. Mode 3. Mean 4. Mean Average Deviation (MAD) about the mean 5. Median

Write down a Context Free Grammar with 8 productions including 4 variables and 3 terminals. i....

Write down a Context Free Grammar with 8 productions including 4 variables and 3 terminals. i. Check whether the Context Free Grammar is ambiguous or not. Justify your answer with necessary example. ii. Finally, construct the reduced grammar corresponding to your generated grammar.

a = [3, -4, 7] b = [-6, 9, 8] c = [4, 0, 8] d...

a = [3, -4, 7] b = [-6, 9, 8] c = [4, 0, 8] d =[7, 1, 7] e = [3, -5, 2, 1] f =[5, -7, -3, 6] g = [3, -4, 4, 3] P = Projection of ex. C = |g|(gf/gf) C = gf/|f| ex. P g --> f = Cgf = C(gf/f) (1/|f|) (f) =( gf/ff)(f) Find a. Pg --> f b. Pa --> 3b + e Find (cross multiply) a. ||a X b|| b. ||g...

x 2 8 5 9 4 3 9 6 7 8 y 3 6 5 7...

x 2 8 5 9 4 3 9 6 7 8 y 3 6 5 7 9 7 4 6 9 9 -5.48x + 0.17 5.48x + 0.17 -0.17x + 5.48 0.17x + 5.48

3-26 (Objectives 3-4, 3-5, 3-6, 3-7, 3-8) For the following independent situations, assume that you are...

3-26 (Objectives 3-4, 3-5, 3-6, 3-7, 3-8) For the following independent situations, assume that you are the audit partner on the engagement: 1. A number of frozen yogurt stores have opened in the last few years and your client, YogurtLand, has experienced a noticeable decline in customer traffic over the past several months that has caused you to have substantial doubt about YogurtLand’s ability to continue as a going concern. 2. Intelligis Electronics is a manufacturer of advanced electrical components....

Simplify the following expression by combining like terms and give your answer. 8(2a − b − 3c) + 3(2a − b) − 4(6 − b)

3, 7, 8, 5, 6, 4, 9, 10, 7, 8, 6, 5 Using the previous question...

3, 7, 8, 5, 6, 4, 9, 10, 7, 8, 6, 5 Using the previous question 's scores, If three points were added to every score in this distribution, what would be the new mean? If three points were added to every score in this distribution, what would be the new standard deviation. Remember, you have already calculated population standard deviation in a previous problem. This problem requires two answers.

Week 2 Ch.3-4 Graded Assignment EX.03.09 EX.03.10.ALGO EX.03.14 EX.03.17 EX.03.20 EX.03.21 CEX.04.10.ALGO EX.04.13.ALGO EX.04.15 EX.04.21.ALGO EX.04.24...

Week 2 Ch.3-4 Graded Assignment EX.03.09 EX.03.10.ALGO EX.03.14 EX.03.17 EX.03.20 EX.03.21 CEX.04.10.ALGO EX.04.13.ALGO EX.04.15 EX.04.21.ALGO EX.04.24 Hide or show questions Progress:11/11 items eBook Calculator Duration-Based Costing Gee Manufacturing produces two models of camshafts used in the production of automobile engines: Regular and High Performance. Gee currently uses an ABC system to assign costs to the two products. For the coming year, the company has the following overhead activities, costs, and activity drivers: Activity Expected Cost Activity Driver Activity Capacity Setups...

Subjects