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 2 years 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...
Problem 3. Let G be the grammar we saw in homework 3: E -> E +...
Problem 3. Let G be the grammar we saw in homework 3: E -> E + T | E - T | T T -> T * F | F F -> ( E ) | x | y Let w be (x + y) * x - y a) Show the leftmost derivation for w in G. Number the rules for G and show the corresponding rule number under each substitution arrow in the derivation. Hint: it may be...
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
Matrix A2= [1 2 3; 4 5 6; 7 8 9; 3 2 4; 6 5...
Matrix A2= [1 2 3; 4 5 6; 7 8 9; 3 2 4; 6 5 4; 9 8 7] Note: TA2 is defined to be a linear transformation that maps any vector x to A2* x. That is TA2 = A2*x. Also the range of the Linear transformation represented by A2 is the same as the column space of A2. l) Find a basis for the null(TA2). m) Find nullity of A2, TA2 and A2tA2. n) Find rank(A2), rank(A2t),...
We are using javaCC notation.This is the full question Given the following grammar: String ::= "A"...
We are using javaCC notation.This is the full question Given the following grammar: String ::= "A" ( "B" | T | V )+ T ::= ("X" T ) | "Y" V ::= ( "C" | "D" )* Which of the following strings are correct according to this grammar? Group of answer choices A C C D X X Y X X Y A B C D A X A B C D A C D C A B C D...
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....
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT