ZuoTi.Pro
Question

Hi, Theory of Computation Could i please get the answer with explanation for the following, thank...

Hi,

Theory of Computation

Could i please get the answer with explanation for the following, thank you.

3. Consider the following CFG with starting variable Sand Σ ={1, 2, 3,4,5,6,7,8,9,0}:

S→MUV

U→N|ε

V→VV| N

N→M| 3| 4| 5| 6| 7| 8| 9| 0

M→1| 2

b. Is this grammar ambiguous or unambiguous? Briefly explain why.

c. Convert the CFG into Chomsky normal form.

engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1

A context-free grammar G is said to be in Chomsky normal form if all of its production rules are of the form: A → BC, or A → a where A,B,C are called variables and a is called terminal.

Before converting a CFG into a CNF

1) Eliminate null productions, if any

2) Eliminate unit producitons, if any

3) Eliminate useless productions, if any

0 0
Add a comment
Know the answer?
Add Answer to:
Hi, Theory of Computation Could i please get the answer with explanation for the following, thank...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • Need help with Theory of Computation. i think ^ is an epsilon. Grade: Name: CSCI 4333...

    Need help with Theory of Computation. i think ^ is an epsilon. Grade: Name: CSCI 4333 Theory of Computation Final December 4th, 2019 Part I. Short answer/problems. Answer all questions. Long rambling answer will be marked as incorrect Point values in parenthsis. 1. Given the following context free grammar over alphabet (a,b): S -> ABa A -> aab | BI B -> Ab | aa a. (6) Show that the grammar is ambiguous for a non-empty string b. (10) Convert...

  • Given the following ambiguous context free grammar (3x20) 1. (a) Explain why the grammar is ambiguous...

    Given the following ambiguous context free grammar (3x20) 1. (a) Explain why the grammar is ambiguous (b) Find an equivalent unambiguous context-free grammar. (c) Give the unique leftmost derivation and derivation tree for the string s generated from the unambiguous grammar above. 2. Construct non-deterministic pushdown automata to accept the following language (20) 3. Convert the following CFG into an cquivalent CFG in Chomsky Normal Form (CNF) (20)-

  • Please answer any 7 of them ТОС Answer any 7 from the followings: 1. Regular expression...

    Please answer any 7 of them ТОС Answer any 7 from the followings: 1. Regular expression to NFA: i) ab(aUb)* ii) (aba U a)*ab 2. Explain and construct a generalized NFA, 3. NFA to regular expression 0 3 91 93 8 a 4. DFA to regular expression 011 5. Explain the rules of pumping lemma briefly with an example. 6. Give an example of right linear grammar and left linear grammar. 7. L(G) = {1*20 m >= 1 and >=1}....

  • 1)Convert the following context free grammar to Chomsky Normal Form S → a X | Yb...

    1)Convert the following context free grammar to Chomsky Normal Form S → a X | Yb X → S | λ Y → b Y | λ 2)Some languages distinguish between uppercase and lowercase in identifiers. What are the pros and cons of this design decision? 3)Use the pumping lemma to prove that the following languages are not regular.     (The alphabet is Σ = {a, b}.) a) L = {an b1 ak: k >= n+ l} b) L = {ww:...

  • Hi, may I get some help with explanation? Thank you Two stars of mass m =...

    Hi, may I get some help with explanation? Thank you Two stars of mass m = 0.60 and M = 74.00 (in units of solar masses) separated by a distance d = 8.00 (in units of AU, the earth-sun distance) revolve in circular orbits about their (common) center of mass as shown in the figure below. С. m. М d What is the orbital period of the smaller star in years?

  • Hi may I get help with explanation? Thank you A 133 kg object and a 640...

    Hi may I get help with explanation? Thank you A 133 kg object and a 640 kg are separated by 0.735 m. Find the magnitude of the net gravitational force exerted by these objects on a 42.0 kg object placed midway between them. Submit Answer Tries 0/6 At an infinitely remote distance, the net gravitational force on the third mass from the other two will be zero. Is there a point along the straight line between the two masses with...

  • Hi, may I get some help with explanation? Thank you Problem 3 A physics student is...

    Hi, may I get some help with explanation? Thank you Problem 3 A physics student is sitting on a rotating platform. He is holding a heavy weight in each of his outstretched hands. At request of his physics instructor(!) he carries out various manoeuvres to try to change his angular velocity. Which of the following scenarios are described correctly? Select True or False. Starting with angular velocity wow he raises his feet, and points them outwards from the chair as...

  • Hi, I understand how to get the Thevenin Resistance of the following circuit but could someone...

    Hi, I understand how to get the Thevenin Resistance of the following circuit but could someone go indepth on how exactly to get the Thevenin Voltage? Thank you! Find the Thévenin equivalent of the network seen by the 3-Ω resistor in Figure P3.52. Use it and voltage division to find the voltage v across the 3-2 resistor. Figure P3.52 2Ω 3 V 2Ω 2 A

  • Hi I was wondering if I could get help with these two questions. Thank you ^_^...

    Hi I was wondering if I could get help with these two questions. Thank you ^_^ Question 2 The hammer throw event in track and field involves spinning a heavy ball attached to a strong wire in a circle, then releasing it at just the right moment in the throw, and at the right angle, to maximize its trajectory away from the starting point. If the hammer thrower shown below is spinning at an angular rate of 3.47 revolutions per...

  • Hi, can I please get some help with this question? Thank you Prove: If lim f(x)...

    Hi, can I please get some help with this question? Thank you Prove: If lim f(x) = L andlim g(x) = M, then lim(f(x) + g(x)) = L+M. x-a xna xa 3. State the converse of #2 above. Next, find a counterexample to the converse of #2 above.

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT