程序代写代做代考 prob2

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