- #1

Mr10k

**Homework Statement**

Let CRYPT be the language of cryptographic expressions of this type that can be generated by the following grammar.

S → E

S → ε

E → E + E

E → E − E

E → SIMPLESUB(E, STRING)

E → VIGENERE(E, STRING)

E → LOCTRAN(E, DIGITS)

E → STRING

In this grammar, the non-terminals are S and E. Treat SIMPLESUB, VIGENERE, LOCTRAN, STRING and DIGITS as just single tokens. For SIMPLESUB, VIGENERE, and LOCTRAN, we allow any nonempty prefix of the function name as well as the full name; e.g., S, Si, Sim, . . . , SimpleSu, SimpleSub are all acceptable lexemes for the token SIMPLESUB.

Prove that CRYPT is not regular.

An example of an input string could be:

Vigenere(LocTran(triantiwontigongolope,3201),bunyip) + muldjewangk

The attempt at a solution

The attempt at a solution

So where I am confused here is that when using the pumping lemma to form a word such that w = xyz, there needs to be a case where w = xy

^{i}z cannot be pumped into CRYPT. The reason why it is confusing is because any STRING is part of CRYPT as stated by the expression E → STRING, so how can I find a word such that by using the pumping lemma I can prove that CRYPT is not regular?