Question

Say that a CFG is minimal if none of its rules can be removed without changing the language generated. Let MINCFG = is a minimal CFG}.

1. Show that MIN_CFG is T-recognizable.
2. Show that MIN_CFG is undecidable.

Short answer

a). MIN_CFG is T-recognizable is proved.

b). MIN_CFG is undecidable is proved.

Step-by-step solution

Turing Machine

A Turing Machine is computational model concept that runs on the unrestricted grammar of Type-zero. It accepts recursive enumerable language. It comprises of an infinite tape length where read and write operation can be perform accordingly.

Solution of problem.

a).

First let us understand Minimal Context Free Grammar MIN_CFG .

MIN_CFG is a CFG where we cannot change or modify any production rule without changing the language from which it is generated.

We can transform MIN_CFG into equivalent grammar in Chomsky Normal form.

For a string of length p, there will be countable number of derivation with 2p-1 steps, for this we will run the generated CFG on a Turing Machine M. This TM M will accept the string which is in the language.

So we will construct the TM M as follows:

Here,$G=MI{N}_{CFG}andw=inputstring$

Create H as equivalent grammar to Chomsky Normal Form G

• Now let n = Length (w)
• Now, if n = 0
• Then check if all derivation at first step in H
  Else
  Then check derivations with 2n-1 steps

• Accept if any of the derivation accept w
  Else
  Reject.

If accept it means that MIN_CFG is Turing Recognizable.