COT6315 Formal Languages and Theory of Computation

Last modified 2004.09.16

Frequently Asked Question (FAQ) List

Regular Expressions, Regular Languages, FSAs

• Q: In some FSA diagrams, there is no transition from a given state on some of the alphabet symbols. Doesn't this contradict the requirement that the transition function be a total function (defined on all of QXS)?
• A: Yes - we often omit a special, absorbing, dead state. Wherever there is a state on which there is no transmission for some symbol a in S, just add an arc labeled a to the dead state. The dead state has a transition to itself on any input symbol.
• Q: Wow! Do I have to draw in the dead state and all those transitions to it when I diagram an FSA?
• A: No - by convention, no valid transition implies non-acceptance, so keep it clean and leave them out.
• Q: In the definition of regular expressions, the null set, 0, and the single length one string sets {a} for a in S, are necessary building blocks. Why isn't e also necessary?
• A: The expression e, corresponding to {e} (the language consisting solely of the null string, which is distinct from 0 = {}, the empty set) is not needed, as it can be derived from the Kleene Closure of 0, 0* = e.

  One way to gain some insight into this is to consider L^k, defined as L^k = { w = w_1 w_2 ... w_k | for all i = 1, 2, ..., k, w_i is in L}. Likewise, for an alphabet S, S^k = { s_1 ... s_k | s_i is in S }, or all the strings of length exactly k. Then S* = S^0 U S^1 U S^2 U .... For any S, S^0 = { e }, and |S^0| = 1. For any S with |S|=n and any k, |S^k| = |S|^k = n^k. Since n^0 = 1, this all makes sense for S^0 and n > 0.

  However, what about 0^0 (in both senses, {}^0 and |{}|^0)? We need to think back on what the definition of a string is. A string of length k may be defined formally as a function from {1,2,...,k} into S. If k = 0, then this is the empty function (the one and only function from {} into S). Now for language L, L^k can be defined formally as the set of all functions from {1,2,...,k} into L. Once again, if either k = 0 or L = 0, then we have the only the empty funtion in that set, so the only string in L^k is e.

CFLs, PDAs, CFGs

• Q: On problem 2.6d, there is a sharp sign (#) in the language - what is that?

  A: The sharp sign is just another alphabet symbol, like a or b or 0 or 1. It is often used as a special delimiter within strings to mark off special substrings so the string is structured.

TMs

Computability, Decidability

• Diagonalization - what is THAT all about?

  The point of diagonalization is twofold: to show the existence of an uncountable set, and to use this to prove that there exist languages that are not decidable, or even computable. The existence of an uncountable set is proven by by showing that there is some element of the uncountable set that is not the image of any natural number under the assumed correspondence. The latter uses the fact that the number of TMs is countable, since each one may be represented by a finite string over some alphabet (the encoding of the TM), but the number of languages is not (it is power set of S* for alphabet S).