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.9k 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
8.3k points
3 votes

Answer:

Step-by-step explanation:

solution

User Pedorro
by
8.6k points
← Prev Question Next Question →

Related questions

Ask a Question
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.5m questions

12.2m answers

Other Questions

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
A car has an initial speed of 10 m/s. It then undergoes a constant acceleration of 0.05 m/s^2 over a distance of 5 km. Determine: a) The car final speed. b) The time needed to travel the 5 km.
Where are all the controls on most circuits?
What claim do ghost hunters make about energy-detecting devices? They can determine how many spirits are in one location. They can produce sounds that may be confused with ghosts. They can sense the presence
The pressure at any point in a static fluid depends only on the Select one a)- depth, surface pressure, and specific weight. b)- specific weight. c)- surface pressure and depth. d)- depth and container
Link Copied!