Let G be a CFG in Chomsky normal form that contains b variables. Show that if G

Question:

Let G be a CFG in Chomsky normal form that contains b variables. Show that if G generates some string with a derivation having at least 2b steps, L(G) is infinite.

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:26 AM

See More Questions

Show that if G is a CFG in Chomsky normal form, then for any string w L(G) of length n 1, exactly 2n 1 steps are required for any derivation of w.
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 .
Let = {0,1}. Show that the problem of determining whether a CFG generates some string 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.
A psychologist shows a list of eight activities to a subject in an experiment. How many ways can the subject pick a first, second, and third activity? a. Identify the total number of objects n and...
What can be said about the signs of the numbers a, b, and c in each case? (A) abc >0 (B) ab/c < 0 (C) a/bc > 0 (D) a2/bc < 0
Vancouver Software Company has just received its sales expense report for January, which follows: Sales Expense Budget Item Amount (LO 3) Sales COMMISSIONS ..........ccccescseeveeesveees $145,000...
1 Explain how choosing to use a particular language in preference to another language in a cross-cultural meeting can affect the interaction and the outcomes of the meeting.
Sora-Tobu-Jutan Technologies wants to estimate the aver-age time it takes to complete the assembly of its new robot vacuum cleaner. After allowing enough time for the workers to learn the new...
[The following information applies to the questions displayed below) Ferns Company began January with 8,000 units of its principal product. The cost of each unit is $8 Merchandise transactions for...
Fernando works 40 hours per week and makes $8.50 per hour. (a) How much money can he expect to earn in 1 year (52 weeks)? (b) If he saves all the money he earns, how long will he have to work to save...
Consider the language B = L(G), where G is the grammar given in Exercise 2.13. The pumping lemma for context-free languages, Theorem 2.34, states the existence of a pumping length p for B. What is...
Give an example of a language that is not context free but that acts like a CFL in the pumping lemma. Prove that your example works. See the analogous example for regular languages in Problem 1.54....
Explain and compare the effects of tillage and manure application on the abundance diversity of soil organisms.
From a square whose side has length $x$, measured in inches, create a new square whose side is 5 in. longer. Find an expression for the difference between the areas of the two squares as a function...
Sketch the requested conic sections in Problems 14-23 using the definition. A circle with radius 5
Find the present value of the ordinary annuities in Problems 21-32. Amount of Deposit m 23. $250 Frequency n semiannually Rate r 8% Time t 30 yr
Characterize the types of investments that are most vulnerable to political risk. Characterize those that are least vulnerable. What factors influence an investments vulnerability? On a scale of 1 to...
Refer to the following tree diagram for a two-stage experiment. Find the probabilities in Problems 1-6. $P(B) $ E E A B C A B C
If N = 4 in the pseudocode in Exercise 29, then what number is displayed when the corresponding code is run? Data from Exercise 29 Declare A As Integer Declare B As Integer Declare N As Integer Set A...
Use the method of Example 4.29 to compute the indicated power of the matrix. 1 0 1
We can define a binary tree representation T² for an ordered general tree T as follows (see Figure 8.21): ¢ For each position p of T, there is an associated position p² of T²....
Describe, in pseudocode, a nonrecursivemethod for performing an inorder traversal of a binary tree in linear time.
Give an O(n)-time algorithm for computing the depths of all positions of a tree T, where n is the number of nodes of T.
Break-Even Sales and Sales to Realize Income from Operations For the current year ending October 31, Yentling Company expects fixed costs of $537,600, a unit variable cost of $50, and a unit selling...
You buy a stock for $35 per share. One year later you receive a dividend of $3.50 per share and sell the stock for $30 per share. What is your total rate of return on this investment? What is your...
Filippucci Company used a budgeted indirect-cost rate for its manufacturing operations, the amount allocated ($200,000) is different from the actual amount incurred ($225,000). Ending balances in the...

Let G be a CFG in Chomsky normal form that contains b variables. Show that if G

Question:

Step by Step Answer:

Proof We prove this by induction on b Base Case b 1 Suppose G is a CFG in Chomsky normal form with o...View the full answer

Introduction to the theory of computation

Students also viewed these Computer science questions