Use undecidability of allcfg to show problem is undecidable

Assignment Help Theory of Computation

Reference no: EM1387003

Let the following problem ALLCFG: Given CFG G, is L(G) = Σ*? This problem is undecidable. (You do not have to prove this).

(a) Is this problem in RE (class of recursively enumerable languages), in core (class of all languages whose complement is in RE), in both, or in neither? Describe your answer.

(b) Use undecidability of ALLCFG to illustrate that following problem is also undecidable: Given PDA M1 and FA M2, is L(M1) = L(M2)?

Reference no: EM1387003

Questions Cloud

Importance of monetary rewards : How does culture affect the importance of monetary rewards? Provide an example to support your position.

What theory or theories of motivation might describe change : Supporting his theory, since 2001, workers in the United States have enhancement their hours worked while tax rates have dropped. What theory or theories of motivation might describe such a change.

Examine various transfer pricing scenarios which tech sonic : Examine various transfer pricing scenarios which Tech Sonic might adopt and the likely impact of each on the Tech Sonic subsidiaries as well as the parent corporation.

Discuss which concepts are the most important : Discuss which concepts are the most important to consider when designing information security policies and procedures.

Use undecidability of allcfg to show problem is undecidable : Use undecidability of ALLCFG to illustrate that following problem is also undecidable: Given PDA M1 and FA M2, is L(M1) = L(M2)?

Illustrate what environmental factors would have the most : Illustrate what environmental factors would have the most impact on these companies? Illustrate what ratio of environmental scanning to internal analysis should each employ

Indicate the genotype and phenotype parent of and offspring : Explain a specific example of a cross between two parents, each homozygous for different traits, which would result in a phenotype that is distinct from either parental phenotype.

Length of time patron spend at the gymnasium : The manager of a local gymnasium has determined that the length of time patron spend at the gymnasium is normal distributed with mean 80minutes and standard deviation 20 minutes. What is the patrons who spend more than 120 minutes at the gymnasium..

Distinguish between a minimization and maximization lp model : Distinguish between a minimization and maximization LP model. How do you know which of these to use for any given problem?

User Account

All Pages