Material since 1st hour exam (e.g., PDAs, CFGs, their equivalence,
non-context-free languages; possibly Kleene discussion; probably little if
anything on Turing machines)
Otherwise similar rules and format to 1st exam, especially open references
Questions?
Decidable Languages
Section 4.1
Decidable problems for regular languages
Acceptance by DFA, NFA, regular expression
Does DFA accept empty string?
Proofs create Turing machines that run DFA and accept or reject according to DFA
final state
Similar proofs for CFLs
Discussion
A big part of the reason for these particular proofs is that they establish much of
a hierarchy of computing power: regular languages are a proper subset of context
free languages, which are a proper subset of Turing decidable languages, which are
a subset (we don’t know if it’s proper yet) of Turing recognizable
languages
Machines corresponding to each class of languages have corrrespondingly greater
computing power
Encodings, particularly encodings of machines
Encoding integers
Encoding 1: alphabet {0,1,-}, integer n encoded as base-2 representation of n
with leading minus if needed e.g., 17 = “10001”, -5 =
“-101”
Encoding 2: represent as base-10
And by the way: since the encoded integers under either of these encodings are
a regular language, and we now know regular languages are Turing decidable, we
can say that the integers are Turing decidable
Encoding of DFA
Transition function = list of ordered pairs
Introduce by marker character, say T
… T ⟨⟨q a⟩ p⟩
⟨⟨…⟩…⟩ ….
q, p are states encoded as integers (see above)
a is an input symbol, encoded as itself (make alphabet for the DFA a subset of
the Turing machine’s alphabet, being careful not to let Turing machine
use any DFA symbols for its own purposes)
Or transition function could also be a table
Which of the following sets are decidable?
The rationals
Yes, encode as integer / integer
(-|ε) DD* / DD* where D = 0|1|2|…|9
The reals
No, because not countable
Therefore they have no encoding as a set of strings over finite alphabet
The rationals union with a finite set of reals?
We create appropriate encodings all the time using special symbols added to our
alphabet for numbers, e.g., π, √, etc.