What is the definition of a computable language?
What is the definition of the intersection of two languages?
Is there such a thing as a computable program? Why or why not?
Suppose that A and B are two computable languages over alphabet {a, b, c, d}. Is A ∪ B computable? Explain.
The difference S − T of two sets S and T is the set {x | x ∈ S and x ∉ T}.
Suppose that S is a computable language over alphabet A = {a, b, c, d}. Is A* − S computable? Explain.
Let B = {p | p is a Java program that contains a static variable of type int called frog}. Is B computable? Why or why not?
A configuration of pieces on an 8x8 chessboard can be described by a string. The configuration tells which piece (if any) is in each square, and whose move is next. Consider the set W of all chessboard configurations where black has a winning strategy. Is W a computable set of strings? (In Chess, if a particular configuration is reached more than once in a game, the game is a draw.)
Let S = {x | x ∈ {a, b, c}* and the length of x is a power of 2}. Prove that S is not a regular language.
Let S = {anbcn | n ≥ 0}. Prove that S is not a regular language.