Prove that this language is not regular (using Pumping Lemma)

[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

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ⁱ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?

 

[KataKoniK]

You are correct that any STRING is part of CRYPT, which means that any word in the language can be pumped. However, this does not necessarily mean that the language is regular.

To prove that CRYPT is not regular, you can use the pumping lemma to show that there exists a word in the language that cannot be pumped. This word will have a length that is greater than the pumping length (p) of the language, and therefore cannot be pumped into CRYPT.

To find such a word, you can use the fact that the grammar allows for any nonempty prefix of the function name for SIMPLESUB, VIGENERE, and LOCTRAN. This means that you can construct a word that is longer than p by repeatedly adding prefixes of these function names to the beginning of the word.

For example, the word Vigenere(LocTran(triantiwontigongolope,3201),bunyip) + muldjewangk has a length of 64, which is greater than p. Therefore, this word cannot be pumped into CRYPT, and the language is not regular.