Consider the following CFG G: S SS | T T aT b | ab Describe

Question:

Consider the following CFG G:

S → SS | T

T → aT b | ab

Describe L(G) and show that G is ambiguous. Give an unambiguous grammar H where L(H) = L(G) and sketch a proof that H is unambiguous.

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For book-img-for-question

Introduction to the theory of computation

ISBN: 978-0470530658

3rd edition

Authors: Michael Sipser

See More Books

Question Posted: Sep 02, 2020 04:31 AM

See More Questions

Let G = (V,,R, hSTMTi) be the following grammar. G is a natural-looking grammar for a fragment of a programming language, but G is ambiguous. a. Show that G is ambiguous. b. Give a new unambiguous...
Let C = {G, x| G is a CFG x is a substring of some y L(G)}. Show that C is decidable. An elegant solution to this problem uses the decider for E CFG .
Show that the problem of determining whether a CFG generates all strings in 1 * is decidable. In other words, show that {G| G is a CFG over {0,1} and 1 * L(G)} is a decidable language.
1) What are the implications of CICs approach to staffing project teams? Is the company using them as training grounds for talented fast-trackers or as dumping grounds for poor performers? 2) How...
Solve Problem -3(4 - x) = 5 - (x + 1)
Sound Investments, Inc., is a large retailer of stereo equipment. The controller is about to prepare the budget for the first quarter of 20x1. Past experience has indicated that 75 percent of the...
9. Consider Example 1. Suppose the February forward price had been $$2.80$. What would the arbitrage be? Suppose it had been $$2.65$. What would the arbitrage be? In each case, specify the...
Sea Star Company manufactures diving masks with a variable cost of $12.50. The masks sell for $ 17.00. Budgeted fixed manufacturing overhead for the most recent year was $396,000. Actual production...
A documentary credit expiring on 1 0 June requires the following documents: Signed commercial invoice indicating goods of German origin Bill of lading evidencing shipment in the middle of May...
Ashley Stamper opened a medical practice. During July, the first month of operation, the business, titled Ashley Stamper, MD, experienced the following events: Jul. 6 Received a contribution of...
Let A = {wtw R | w, t {0,1} * and |w| = |t|}. Prove that A is not a CFL.
Let = {0,1} and let B be the collection of strings that contain at least one 1 in their second half. In other words, B = {uv| u * , v * 1 * and |u| |v|}. a. Give a PDA that recognizes B. b....
Determine whether the graph represents a function. If it does represent a function, give its domain and range. 2- -2 2 -2-
IFRS Financial Statements Thomson Reuters is a global information company created by the 2008 merger of the Thomson Corporation, a Canadian company, with the Reuters Company, a United Kingdom-based...
Burgess Services Co. experienced the following events in 2011: 1. Provided services on account. 2. Collected cash for accounts receivable. 3. Attempted to collect an account and, when unsuccessful,...
In Exercises 13 and 14, use the box-and-whisker plot to identify the five-number summary. 0 2 5 8 10 ++ ++ 0 1 2 3 4 5 6 7 8 9 10 11
In a test of the effect of dampness on electrical connections, 80 electrical connections were tested under damp conditions and 130 were tested under dry conditions. Twenty of the damp connections...
Zelta Ltd. is a medium-size company involved in providing a range of specialized products and services for the aerospace industry. Just over a year ago, external consultants undertook a major review...
Draw a flowchart for the pseudocode in Exercise 15. Data from Exercise 15 Declare Number As Integer Set Number = 2 While Number != 0 Write Number Set Number Number - 1 End While
Describe a job you have had in the past or a job you are very familiar with. Indicate the negative aspects of the job and how it could be improved with current human resource management techniques.
Alice has three array-based stacks, A, B, and C, such that A has capacity 100, B has capacity 5, and C has capacity 3. Initially, A is full, and B and C are empty. Unfortunately, the person who...
Suppose you have three nonempty stacks R, S, and T. Describe a sequence of operations that results in S storing all elements originally in T below all of Ss original elements, with both sets of those...
Show how to use the transfer method, described in Exercise R-6.4, and two temporary stacks, to replace the contents of a given stack S with those same elements, but in reversed order.
Famas Llamas has a weighted average cost of capital of 8.8 percent. The companys cost of equity is 12 percent, and its pretax cost of debt is 6.8 percent. The tax rate is 22 percent. What is the...
The common stock of a company paid 1.32 in dividens last year. Dividens are expected to gros at an 8 percent annual rate for an indefinite number of years. A) If the company's current market price is...
(1 point) Bill makes annual deposits of $1900 to an an IRA earning 5% compounded annually for 14 years. At the end of the 14 years Bil retires. a) What was the value of his IRA at the end of 14...

Consider the following CFG G: S SS | T T aT b | ab Describe

Question:

Step by Step Answer:

Introduction to the theory of computation

Students also viewed these Computer science questions