3a) Let ?={????:0≤?≤?}. How many of the following strings are in ?∗? ?,??????,????,???,????,????,?????,???? 3 4 5...

3a) Let ?={????:0≤?≤?}. How many of the following strings are in ?∗?

?,??????,????,???,????,????,?????,????

Let ? be any NFA with a single final state. If we convert ? into a right-linear grammar ?, the number of production rules in ? will be equal to

number of transitions in ?

number of states in ? plus 1

number of states in ?

number of transitions in ? plus 1

Solutions

Expert Solution

3a)The answer of this question is 3.

Description of the Answer: As the question is given the automata accepts the string a_ib_j if 0<=i<=j.So,clearly the string will be starting from a or b .If b comes once a can't come,as the rule given and number of a must be less than or equal to the number of b .Check the answers now and match the follwoing criterias.

Lambda : in which number of a and b is 0.So,obviously it will be accepted.

aaaaab can't be accepted as number of a is not less than number of b.

and after b , a can't come so we can eliminate abab,babb,baba,abaab.

now for the others bbb,aabb ,these are obviously valid and will be accepted, as number of a is less than or equal to number of b.

so the correct answer will be 3(lambda,bbb,aabb).

b)The answer of this question is option no 4,number of transition in M plus 1.

Description:The right linear grammer is one type of grammer where A->aB means from A state by giving terminal a we can reach to a state B.For the NFA (Nondeterministic Finite Automaton) as the transition given we can easily convert it into right linear grammer .We will put the statring state first and from this then terminal symbol on the right and after that the destination state.Let me give you one example:bBut while we are converting from NFA to right linear grammer the final state will get a production of epsilon.As this is a final state the grammer indicates where to stop.That is why As per the question given the number of final state is 1.So ,from NFA the right linear grammer will have excess production rules by 1 only.That gives 4th as the right answer.The number of productions in right linear grammer will be number of productions in the NFA plus 1 as the number of final state is 1.One extra final state to epsilon production.

venereology answered 1 year ago

Next > < Previous

Related Solutions

Let 3x3 matrix A = -3 0 -4 0 5 0 &nb

Let 3x3 matrix A = -3 0 -4 0 5 0 -4 0 3 a) Find the eigenvalues of A and list their multiplicities. b) Find a basis, Bi, for each eigenspace, E(i). c) If possible, diagonalise matrix A. (i.e find matrices P and D such that Pinv AP = D is diagonal).

Let A = (3, 4), B = (0, −5), and C = (4, −3). Find equations...

Let A = (3, 4), B = (0, −5), and C = (4, −3). Find equations for the perpendicular bisectors of segments AB and BC, and coordinates for their common point K. Calculate lengths KA, KB, and KC. Why is K also on the perpendicular bisector of segment CA?

This is one question about 14-bit strings How many 14-bit strings that have more 0’s than...

This is one question about 14-bit strings How many 14-bit strings that have more 0’s than 1’s? How many 14-bit strings that have even number of 0’s? How many 14-bit strings that have no consecutive three 0’s in a row?

4) Let ? = {2, 3, 5, 7}, ? = {3, 5, 7}, ? = {1,...

4) Let ? = {2, 3, 5, 7}, ? = {3, 5, 7}, ? = {1, 7}. Answer the following questions, giving reasons for your answers. a) Is ? ⊆ ?? b)Is ? ⊆ ?? c) Is ? ⊂ ?? d) Is ? ⊆ ?? e) Is ? ⊆ ?? 5) Let ? = {1, 3, 4} and ? = {2, 3, 6}. Use set-roster notation to write each of the following sets, and indicate the number of elements in...

Consider the following page reference string: 0, 1, 2, 3, 1, 0, 4, 5, 1, 0,...

Consider the following page reference string: 0, 1, 2, 3, 1, 0, 4, 5, 1, 0, 1, 2, 6, 5, 2, 1, 0, 1, 2, 5 How many page faults would occur for the following replacement algorithms, assuming one, three, five, and seven frames? Remember that all frames are initially empty, so your first unique pages will cost one fault each. Optimal replacement LRU replacement CLOCK replacement FIFO replacement

Given the following dataset x 1 1 2 3 4 5 y 0 2 4 5 ...

Given the following dataset x 1 1 2 3 4 5 y 0 2 4 5 5 3 We want to test the claim that there is a correlation between xand y. The level of cretaine phosphokinase (CPK) in blood samples measures the amount of muscle damage for athletes. At Jock State University, the level of CPK was determined for each of 25 football players and 15 soccer players before and after practice. The two groups of athletes are trained...

Given the following dataset x 1 1 2 3 4 5 y 0 2 4 5...

Given the following dataset x 1 1 2 3 4 5 y 0 2 4 5 5 3 We want to test the claim that there is a correlation between xand y. (a) What is the null hypothesis Ho and the alternative hypothesis H1? (b) Using α= 0.05, will you reject Ho? Justify your answer by using a p-value. (c) Base on your answer in part (b), is there evidence to support the claim? (d) Find r, the linear correlation...

Part I: Numerical Integration Evaluate the following integrals: i. ∫4(1−?−4?3 +2?5)?? 0 ii. ∫3(?2??)?? 0 a)...

Part I: Numerical Integration Evaluate the following integrals: i. ∫4(1−?−4?3 +2?5)?? 0 ii. ∫3(?2??)?? 0 a) Analytically b) Multiple application of Trapezoidal rule n = 4. c) Simpson’s 1/3 rule for n = 4. d) Simpson’s 1/3 and Simpson’s 3/8 rule for n = 5. e) Determine the true percent relative error.

Let the following be the supply and demand for coconuts. P 2 3 4 5 6...

Let the following be the supply and demand for coconuts. P 2 3 4 5 6 7 8 9 10 11 12 Qs 100 200 300 400 500 600 700 800 900 1000 1100 QD 550 500 450 400 350 300 250 200 150 100 50 Now imagine that there is a price ceiling on coconuts at $3 but in order to prevent wasting peoples' time by making them wait in line, the government hands out ration coupons to people....

3. How many strings can be made using 9 or more letters of MISSISSIPPI?

Subjects