Final answer:
The language L_1 = { a^n: n is prime } is proven to be non-regular by applying the Pumping Lemma. Assuming it is regular leads to a contradiction, hence showing that it cannot be expressed by a finite automaton or regular expression.
Step-by-step explanation:
To show that the language L_1 = { an: n is prime } is not a regular language, one can apply the Pumping Lemma, which is a fundamental concept in the theory of formal languages and automata within computer science. According to the Pumping Lemma, for any regular language, there exists an integer p (the pumping length) where if s is any string in the language of length at least p, then s can be divided into three parts, x, y, and z, satisfying the conditions: s = xyz, |xy|≤ p, |y| > 0, and for each i ≥ 0, the string xyiz is also in the language.
To prove L_1 is not regular, assume for the sake of contradiction that it is. Then, there must exist a pumping length p. Choose a string s = aq where q is a prime greater than p. According to the Pumping Lemma, s can be split into xyz, with y being non-empty. However, if we pump y to y2, the resulting string would have a length of q + |y| which is no longer prime, thus not in the language, leading to a contradiction and implying that L_1 cannot be regular.