1. (12 points) Consider the following context-free grammar G and answer the following questions. S A1B...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
1. (12 points) Consider the following context-free grammar G and answer the following questions. S A1B A 0A | B B1 | (a) What are the variables, terminals, and the start variable of G? (b) For each of the following, answer True or False i. S 00011 ii. S=> 10101 (c) For the string 00111, give both the leftmost derivation and the parse tree. (d) What language does this grammar generate? 2. (12 points) Consider the following grammar SaS aSbS This grammar is ambiguous. Show in particular that the string aab has two: (a) Leftmost derivations. (b) Parse trees. 3. (12 points) Design CFGs for the following languages. (a) {amn | n 0,m 1}. (b) {w | w * and w=w, where w is the reverse of w}. Here = {a,b}. For example, abba, bab, and baab are all in the language, but bbaa is not. Note that e is also in the language. (c) {abek |i=jor i = k, where i, j, k 0}. 1. (12 points) Consider the following context-free grammar G and answer the following questions. S A1B A 0A | B B1 | (a) What are the variables, terminals, and the start variable of G? (b) For each of the following, answer True or False i. S 00011 ii. S=> 10101 (c) For the string 00111, give both the leftmost derivation and the parse tree. (d) What language does this grammar generate? 2. (12 points) Consider the following grammar SaS aSbS This grammar is ambiguous. Show in particular that the string aab has two: (a) Leftmost derivations. (b) Parse trees. 3. (12 points) Design CFGs for the following languages. (a) {amn | n 0,m 1}. (b) {w | w * and w=w, where w is the reverse of w}. Here = {a,b}. For example, abba, bab, and baab are all in the language, but bbaa is not. Note that e is also in the language. (c) {abek |i=jor i = k, where i, j, k 0}.
Expert Answer:
Answer rating: 100% (QA)
1 Consider the following contextfree grammar G G V R S where Variables V S A B Terminals 0 1 c Start ... View the full answer
Related Book For
Income Tax Fundamentals 2013
ISBN: 9781285586618
31st Edition
Authors: Gerald E. Whittenburg, Martha Altus Buller, Steven L Gill
Posted Date:
Students also viewed these programming questions
-
A client of yours has decided to take their CPP retirement pension early at the age of 60. Assuming they are entitled to a CPP Pension of $1,306.58 at normal retirement age, what will their pension...
-
North Mountain's currrent ratio is 148 It is considering issuing $ 31 million in bonds to purchase a new manufacturing facility Its current liabilities are $ 34 million but the new debt would...
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
Consider a static (one-period), closed economy with one representative consumer, one rep- resentative firm, and a government. The level of capital K and government expenditures G in the economy are...
-
In a particular region of space there is a uniform magnetic field B. Outside this region, B = 0. Can you inject an electron from outside into the field perpendicular clearly so that is will move in a...
-
The cost of producing x wheeled picnic coolers is given by C(x) = 200 + 50x - 50 ln x x 1 Find the minimum average cost.
-
Show that the stochastic process \[e^{\int_{0}^{t} c(s) d B_{s}-\frac{1}{2} \int_{0}^{t} c^{2}(s) d s}\] is a martingale for any deterministic function \(c(t)\). Does the result change if \(c(t,...
-
a. Clearwater Company budgets sales of $3,400,000, fixed costs of $750,000, and variable costs of $2,244,000. What is the contribution margin ratio for Clearwater Company? b. If the contribution...
-
On January 1, JKR Shop had $550,000 of beginning inventory at cost. In the first quarter of the year, it purchased $1,690,000 of merchandise, returned $24,100, and paid freight charges of $38,600 on...
-
Based on Figure, Joe, one of your systems analysis team members, made the following entry for the data dictionary used by Marilyns Tours: DATA ELEMENT = TOURIST* * * * PAYMENT ALIAS = TOURIST PAY...
-
Financial Statements of Peter Ltd. and its 80%-owned subsidiary Sam Ltd. as at December 31, Year 5, are presented below: Statement of Financial Position as at December 31 Year 5 Peter Ltd Sam Ltd...
-
a. What is operating income? b. What is net income, and how does it differ from operating income? c. Why is net income called the bottom line? d. What is the difference between net income and cash...
-
How are the following types of revenue reported on the income statement? (a) discounts from charges, (b) charity care, (c) bad debt losses resulting from a change in circumstances.
-
How does data flow for a stream opened for writing or appending?
-
What did Park Ridges 2021 statement of cash flows tell us?
-
Suppose that St. Vincents Hospital has a target capital structure of 35 percent debt and 65 percent equity. Its cost of equity estimate is 13.0 percent and its cost of tax-exempt debt estimate is 7.5...
-
1. Name the following compounds Br te a) b) COH 2. Give the common and IUPAC name the following compound OH NH I
-
Pappa's Appliances uses the periodic inventory system. Details regarding the inventory of appliances at January 1, purchases invoices during the year, and the inventory count at December 31 are...
-
Mallory Corporation has a calendar year-end. The corporation has paid estimated payments of $10,000 during 2012 but still owes an additional $5,000 for its 2012 tax year. a. When is the 2012 tax...
-
During 2012, Tom sold Sears stock for $10,000. The stock was purchased 4 years ago for $13,000. Tom also sold Ford Motor Company bonds for $35,000. The bonds were purchased 2 months ago for $30,000....
-
Kathy Kennedy (age 44) is a single taxpayer and she lives at 212 North Pine Way, Payson, AZ 85541. Her Social Security number is 467-98-9784. Kathy's earnings and income tax withholding as the...
-
There is another possible explanation for purchased goodwill appearing in a sole proprietor's statement of financial position. What do you think it might be?
-
Why do the assets need to be revalued in these cases? The business has not been sold.
-
The shown partners have always shared profits and losses in the ratio: Holt 4; Stott 2: Young 1. From 1 January the assets were to be revalued as the profit sharing ratios are to be altered soon. The...
Study smarter with the SolutionInn App