Some Unsolvable Problems on Grammars                 

 

 

1. Consider a TM M that accepts an RE set that is not Recursive and an arbitrary input U.

2. Consider a grammar G_U :

          The nonterminals: The entire alphabet of  S(M), S, V

The terminals:       a  (only)

Production rules:

          All of  S(M) and

          S -> h Q1 B U h

          h Q0 h -> V

          V -> a V

          V -> a

Note that this grammar depends not only on a TM but also on a possible input

String.   

3. M accepts U  <->  L(G_U ) = { a^m | m>=1}

                   <->  L(G_U ) <> The Empty-set

                   <->  L(G_U ) is infinite

                   <->   “a” is in L(G_U )

 

Above construction of  G_U  leads to:

 

THM 6.1, page-192

Given a grammar G, there is no algorithm for deciding whether or not

1. L(G) is empty  (Grammar Emptiness Problem)

          2. L(G) is infinite (Grammar Infinity Problem)

          3. an arbitrary string is in L(G) (Membership Problem)

 

THM 6.2, page-192 (Grammar Equivalence Problem and Grammar Subset Problem)

Given two grammars, G1 and G2, there is no algorithm for deciding whether

          1.   L(G₁)  =  L(G₂)

          2.   L(G₁)  <=  L(G₂)

Proof:

          1. Let  L(G₁)= { a^m  | m>=1}

              That is: G₁ has following two production rules:

                   S  ->  a S

                   S  ->  a

          2. Let  G₂  be above grammar constructed from an arbitrary TM and an arbitrary

              Input string.

          3. M accepts an input string U  <-> L(G₂) = L(G₁) <-> L(G₁) <= L(G₂)

 

Note that Grammar Proper Subset Problem is also unsolvable:

          L(G₂)  <  L(G₁)

          when  G₁     has following production rules:

                   S -> a S

                   S ->  l  (empty-string)