New answers tagged pumping-lemma
1
As all words of length $>1$ and only consisting of a's should be contained in L2, there is a simple finite automaton that recognizes it. So your attempt at using the pumping lemma is futile, as the pumping lemma only helps you prove that a language is irregular if it is, and doesn't tell you anything about languages that are regular.
Maybe I'm also ...
2
Here is yet another proof. It is known that the number of integers at most $n$ which are the product of two primes is $o(n)$, see for example this answer, which gives the asymptotic $\frac{n\log\log n}{\log n}$. This means that your language is infinite yet has vanishing asymptotic density. This is impossible for a regular unary language.
1
According to the Fundamental Theorem of Arithmetic, any integer $>1$ can be written as a product of one or more primes (in a unique way). So, it seems that your language can be simplified as $\{a^n\mid n\geq 2\}$.
3
Just pump up $(M+1)$ $y$'s. Now you get $xy^{M+1}z=a^{(M+1)j+M-j}=a^{M(j+1)}$. Since $M$ is a product of two primes, $M(j+1)$ is a product of at least 3 primes, so $a^{M(j+1)}\notin L_1$, which proves $L_1$ is not regular by the pumping lemma.
1
There is an alternative to the “pumping” lemma which I find easier: After each possible input, determine the set of continuations that would complete a string of the language. You can use each of those sets as a state in the finite state machine for the language, so if there is a finite number of those sets then the language is regular- if there are ...
2
The subset of all palindromes in L is obviously not usually regular, take the simple example $a^*ba^*$ where the subset of palindromes $a^nba^n$ is not regular.
Assume you have an FSM for L (that is an FSM describing and defining L). You can take that FSM and use a simple algorithm to determine if w is in M:
Given a state S, define succ(S, a) as the state ...
Top 50 recent answers are included
