Register
Say that a variable A in CFG G is necessary if it appears in every derivation of some string w ∈ G. Let NECESSARY CFG = hG, Ai. a. Show that NECESSARY CFG is Turing-recognizable. b. Show that NECESSARY
27.0k views
5 votes
Say that a variable A in CFG G is necessary if it appears in every derivation of some string w ∈ G. Let NECESSARY CFG = A is a necessary variable in G.

a. Show that NECESSARY CFG is Turing-recognizable.
b. Show that NECESSARY CFG is undecidable.

User Shajji
by
7.2k points

2 Answers

4 votes

Answer:

NECESSARY CFG is Turing-recognizable and undecidable already shown bellow

Step-by-step explanation:

Say that a variable A in CFG G is necessary if it appears in every derivation of some-example-1
Say that a variable A in CFG G is necessary if it appears in every derivation of some-example-2
User James Tanner
by
7.7k points
3 votes

Answer:

Step-by-step explanation:

solution

User Pedorro
by
8.2k points
Ask a Question
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

8.8m questions

11.4m answers

Other Questions

A piston-cylinder device fitted with stops in the cylinder walls contains 2.1 kg of water initially at 150 kPa and 30 °C. Heat is transferred to the system until the final temperature reaches 250 °C. The
4. Which of the following is the first thing you should do when attempting to park? A. Securing the parking spot by standing in it B. Turning on your hazard lights C. Confirming the space can fit your
A water towers lowest point is 405 ft and the main line is 6 feet below the ground. The ground elevation is at 276 ft. The main line travels 2.9 miles. The pipe will travel through the following flanged
An activated sludge plant is being designed to handle a feed rate of 0.438 m3 /sec. The influent BOD concentration is 150 mg/L and the cell concentration (MLVSS) is 2,200 mg/L. If you wish to operate the
The bulk modulus of a fluid if it undergoes a 1% change in volume when subjected to a pressure change of 10,000 psi is (a) 0.01 psi (b) 0.001 psi (c) 0.00001 psi (d) 0.000001 psi (e) none of these
Link Copied!