14. If L is recursive, is it necessarily true that L + is also recursive?
15. Choose a particular encoding for Turing machines, and with it, find one
element of the language in Theorem 11.3.
16. Let S 1 be a countable set, S 2 a set that is not countable, and S 1 ⊂ S 2 . Show
that S 2 must then contain an infinite number of elements that are not in S 1 .
17. In Exercise 16, show that in fact S 2 − S 1 cannot be countable.
18. Why does the argument in Theorem 11.1 fail when S is finite?
19. Show that the set of all irrational numbers is not countable.
11.2 Unrestricted Grammars
To investigate the connection between recursively enumerable languages and
grammars, we return to the general definition of a grammar in Chapter 1. In
Definition 1.1 the production ruleswere allowed to take any form,but various
restrictions were later made to get specific grammar types. If we take the general
form and impose no restrictions, we get unrestricted grammars.
Definition 11.3
A grammar G =(V, T, S, P) is called unrestricted if all the productions are of
the form
u → υ,
where u is in (V ∪ T) + and υ is in (V ∪ T)*.
In an unrestricted grammar, essentially no conditions are imposed on the
productions. Any number of variables and terminals can be on the left or right,
and these can occur in any order. There is only one restriction: λ is not allowed
as the left side of a production.
As we will see, unrestricted grammars are much more powerful than
restricted forms like the regular and context-free grammars we have studied so
far. In fact, unrestricted grammars correspond to the largest family of languages
15. Choose a particular encoding for Turing machines, and with it, find one
element of the language in Theorem 11.3.
16. Let S 1 be a countable set, S 2 a set that is not countable, and S 1 ⊂ S 2 . Show
that S 2 must then contain an infinite number of elements that are not in S 1 .
17. In Exercise 16, show that in fact S 2 − S 1 cannot be countable.
18. Why does the argument in Theorem 11.1 fail when S is finite?
19. Show that the set of all irrational numbers is not countable.
11.2 Unrestricted Grammars
To investigate the connection between recursively enumerable languages and
grammars, we return to the general definition of a grammar in Chapter 1. In
Definition 1.1 the production ruleswere allowed to take any form,but various
restrictions were later made to get specific grammar types. If we take the general
form and impose no restrictions, we get unrestricted grammars.
Definition 11.3
A grammar G =(V, T, S, P) is called unrestricted if all the productions are of
the form
u → υ,
where u is in (V ∪ T) + and υ is in (V ∪ T)*.
In an unrestricted grammar, essentially no conditions are imposed on the
productions. Any number of variables and terminals can be on the left or right,
and these can occur in any order. There is only one restriction: λ is not allowed
as the left side of a production.
As we will see, unrestricted grammars are much more powerful than
restricted forms like the regular and context-free grammars we have studied so
far. In fact, unrestricted grammars correspond to the largest family of languages