Question

Determining whether languages are finite, regular, context free, or recursive

1. (Each part is worth 2 points) Fill in the blanks with one of the following (some choices might not be used): a) finite b) regular but not finite d) context-free but not deterministic context-free e) recursive (that is, decidable) but not context-free f) recursively enumerable (that is, partially decidable) but not recursive g) not recursively enumerable Recall that if M is a Turing machine then "M" (also written as encode(M)) is its represen- tation as a string of tape symbols, and if w is a possible input to M then w" (also written as encode(w)) is its representation as a string of tape symbols. 1.6) The language (1"0"1" : n 20) is 1.7) The language (1, 11,00,01, 100, 1010) is 1.8) The language {1"Ojm : mメn} is nn1n.

Answer 1

1.6) recursive but not context-free.

1.7) finite.

1.8) deterministic context-free but not regular.