Others are more involved, although for these I try to indicate in the accompanying comments what the difficulties are. Write regular expressions for the following languages. Show that if L 1 is a nonregular language and L 2 is a finite language, then their union is nonregular. Give an example to show that the union of two nonregular languages can be regular. Show furthermore that there is an unambiguous grammar for R in which each regular expression is derived in a manner consistent with the precedence rules.
L is context-free.
The definition is the same as that of a one-dimensional TM, but we permit the reading head to move up and down and well as to the right and left. At the start of computation, the input string is written in the lowest row of cells, beginning at the left end of the grid, and all the other cells are blank. Here is a problem from the textbook. Show that a language L is decidable if and only if there is a TM that enumerates all the elements of L in order of increasing length. That is, first the elements of L of length 1, then those of length 2, etc.