prob2
Problem 2
Proof
Suppose CRYPT is regular. Then it has a Finite Automaton that accepts it. The number of states
of it is N.
Let w := LOCTRAN(LOCTRAN(LOCTRAN(…LOCTRAN(STRING, DIGITS), DIGITS) , DIGITS), DIGITS) in
which LOCTRAN is applied N times. Since , by the Pumping Lemma for Regular
Languages, we can partition w into strings x,y,z, w = xyz, y is non-empty and |xy| ≤ N, for all i ≥
0 we have . But from the grammer of CRYPT, we can’t have nonempty y such
that for all i ≥ 0, . Because the repeating can only happen in E -> E + E or E -> E –
E, but no ‘+’ and ‘-‘ in w.
Thus we have contradiction, CRYPT is not regular.
Problem 2
Proof