4
This type of question often rises when starting to learn the theoretic aspect of computer science.
The answer, which may seem unfortunate at first, is that there is no algorithmic way of determining whether a language is regular. Moreover, there will never be an algorithmic way, no matter what advances in computers the future may bring, and how many clever ...
4
I'm not aware of any completely "algorithmic" method to decide whether a language is regular.
For the specific language you are interested in, you can start by observing that it can be written as combination of unions and intersections of a finite number of regular languages:
$$
\bigcap_{\alpha \in \Sigma} \left( L_{2,\alpha} \cup L_{3,\alpha} \right),
$$
...
3
For a language $L$, denote $P(L)$ as the minimum pumping length of $L$. It is implied that $P(L)\ge1$.
Proposition. Let $A,B$ be two languages with finite minimum pumping lengths. We have $P(AB)\le P(A)+P(B)-1$. Moreover, there exist regular $A,B$ such that the equality holds.
Proof. Let $w=w_Aw_b\in AB$, where $w_A\in A, w_B\in B$. Assume $|w|\ge P(A)+P(B)...
3
Lets assume towards contradiction that L is regular.
Then, by closure properties, we have $\bar L$ is regular, and thus also $\bar L \bigcap (a^*b^*c^*)$ is regular. But calculating it, we find out $\bar L \bigcap (a^*b^*c^*)=\{a^nb^nc^n\}$ is not regular.
3
A unary language (i.e., a subset of $0^*$) $L$ is regular iff the set $S = \{ n : 0^n \in L \}$ is eventually periodic. In particular, if $L$ is regular then either $S$ is finite or $S$ has positive density (in the following strong sense: $|S \cap [n]|/n$ converges to a positive number). However, in your case the set $S$ is infinite yet has density zero.
In ...
3
You have to find an infinite set of strings $s_i$ such that for every two strings $s_i ≠ s_j$, there is a string $t_{ij}$ such that exactly one of $s_i t_{ij}$ and $s_j t_{ij}$ is in the language, and the other is not.
Now if you look at $a^n$ and $a^m$, n ≠ m, can you find a string t such that exactly one of $a^n t$ and $a^m t$ is in the language, and the ...
3
Since I see questions about the pumping lemma on this site quite often, I decided to write a bit of a longer answer hoping that it helps people "get" the PL rather than just treating it as a "plug-n-chug" tool given to us by the gods of math.
Understanding the PL
I think the best way to go about it is to basically (re-)derive the lemma.
...
3
It will be convenient to distribute the concatenation to get the equivalent RE
$$0(1111)^\ast + 0(00)^\ast + 0001(1111)^\ast + 0001(00)^\ast.$$
Now note that any such string can be writen as $s = s_i(s_r)^\ast$ where $s_i$ denotes the initial part (i.e. $0$ or $0001$) and $s_r$ denotes the repeated part (i.e. $1111$ or $00$).
We see that $s$ can be pumped if ...
3
You said:
If I understand correctly, $x$ and $z$ are basically anything on the 2
sides of the string $y^p$ that we're pumping and thus can be anything
in 𝐿.
This is not true. The pumping lemma suggests that for every long enough word $w$ such that $w\in L$, there is a partition of $w$ into three words $w = xyz$ such that the three conditions of the lemma ...
2
Let us denote by $L_b$ the language of all words with equally many 0s and 1s, starting with $b \in \{0,1\}$. By symmetry, $L_0$ is regular iff $L_1$ is regular. Therefore, if $L_0$ is regular then so is $L_0 \cup L_1 \cup \{\epsilon\}$, which is the language of all words with equally many 0s and 1s. The latter is known to be non-regular, hence $L_0$ must be ...
2
Use the pumping lemma, and note that you can select the string to be pumped (the pumping lemma states that all strings in the regular language at least $p$ long can be pumped).
Assume $L$ is regular, so it satisfies the pumping lemma, let $p$ be the constant of the lemma, which we know is at least 1. Select the string $0^p 1^p$, which certainly is in the ...
2
This is one of those trap questions where $L_2$ can actually be written in a different way that makes it obvious that it is a regular language. See if you can figure out what $L_2$ is "really doing", and the answer will become obvious.
Solution:
2
To apply the pumping lemma for regular languages:
You assume some pumping length $p > 0$: Suppose a pumping length $p$.
You pick a string $s$ such that $|s| \geq n$: Indeed, $a^pb^p$ is a good one since $|a^pb^p| = 2p \geq p$.
Now, you have to consider all the partitions of $s$ as $xyz$, such that
$|y|>0$ and
$|xy| \leq p$.
In this case, the 2nd ...
2
How would you prove that L is regular? You can prove it by giving a regular expression or a finite state machine. And we know that finite languages are regular, and if L1 and L2 are regular then the complement of L1, and the union or intersection of L1 and L2 are regular, and with that finite set operations between regular languages are regular.
How would ...
2
Assume a finite state machine. Since the state machine is finite there are n != m where $a^n$ and $a^m$ end up in the same state. So $a^nb^n$ and $a^m b^n$ both end up in the same state, so are either both in L or both not in L, which contradicts the definition of L.
2
Just show that after processing $0^n$ and $0^{n’}$ with n != n’ you must have reached two different states. (Which is easy: In one state, processing $1^n$ leads to an accepting state, in the other state it doesn’t). Therefore there is no finite set of states.
Or you just take the pumping lemma, p arbitrary large, and w = $0^p 1^p$. Which makes y = $0^k$ ...
2
Suppose that $L$ is regular. Take the complement of $L$ and intersect it with $a^*b^*c^*$. You are left with $M = \{a^n b^n c^n \mid n \ge 0\}$. Due to the closure properties of regular languages, $M$ is also regular.
Let $n_0$ be the pumping length of $M$. By the pumping lemma there is some $x \in \{1, \dots, n_0\}$ such that all words $a^{(n_0-x)+ix} b^{...
2
Suppose that $L$ is regular, and let $p$ be the pumping lemma constant. Let $w = a^p b^{p+p!} c^{p+p!} \in L$. By the pumping lemma, we can write $w = xyz$ so that $|xy| \leq p$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$. Since $|xy| \leq p$, the subword $y$ is composed entirely of $a$'s, say $y = a^t$, where $t \neq 0$. Then $xy^{1+n!/t}z = a^{...
2
$\{ww\mid w\in\{0,1\}^*\}$ not being context-free does not imply every subset is also not context-free. In this case, $0^n1^n0^n1^n$ passes the pumping lemma, since it can be written as follows $0^p1^p0^p1^p=0^p1^{p-1}1^n0^n0^{p-1}1^p$.
2
the union of 2 non-regular languages can be regular.
The trivial example is any non-regular language L and its complement. The union of those two is the set of all strings, which is a regular language.
There for the conclusion $L1, L2 \notin Regular \implies L1\cup L2 \notin Regular$ does not follow.
2
Proof:
Lets assume L is regular. Then we know that L must meet the requirements of the pumping lemma.
So let p the pumping number.
Let $w=a^pcb^p$. $w$ is obviously of the length p and is in L. Therefore it should be possible to split w into three pieces xyz such that $|y|>0,|xy|\leq p,xy^iz$ is in L $\forall i \in N$.
Because $|xy|\leq p$ $y $ can only ...
2
Ok I will split the answer into two parts, one for each of your questions \ concerns \ confusions:
Q: Are we allowed to use the pumping lemma if we chose a specific decomposition, or do we need to show for all decompositions?
A: The pumping lemma states, $\exists p.\forall w.|w|\ge p \rightarrow \exists x,y,z.w=xyz \land\text{ they are a valid decomposition ...
2
Your grammar generates the language $\{a^ib^jc^kd^\ell \mid i,j,k,l \geq 1\}$, which is larger than $\{a^nb^nc^nd^n \mid n \geq 1\}$. For example, your grammar generates $abcdd$, which is not of the form $a^nb^nc^nd^n$.
That said, you can generate $\{a^nb^nc^nd^n \mid n \geq 1\}$ using a context-sensitive grammar. Moreover, unrestricted grammar can generate ...
2
Two points:
the reasoning is incomplete: you need to show that pumping $y$ in the two first cases also leads to elements outside $L$
the reasoning does not use $ |xy|<d$ which entails that only the first case occurs.
But it is not wrong. If you want to ignore $|xy|<d $ then you need to argue the three cases. The first case holds because deleting $y$ ...
2
This language L = { w | w has equal number of as and bs and w≠ ε (since you put a +) } is a CFL
A PDA would work as follows :
On reading a :
If the stack is empty or the top of the stack is a push a
If the top of stack is b pop b push nothing
On reading b :
If the stack is empty or the top of the stack is b push b
If the top of stack is a pop a push nothing
...
2
Assume that $L$ is regular. Suppose that the pumping constant is $q$, and let $p$ be a prime larger than $q$. Consider the word $w = 0^{p+1}1^p \in L$. According to the pumping lemma, we can write $w = xyz$, where $|xy| \leq q$, $y \neq \epsilon$, and $xy^tz \in L$ for all $t \geq 0$. Let $y = 0^i$, where $1 \leq i \leq q < p$. Then
$$
xy^{t+1}z = 0^{p+1+...
2
Suppose that $L$ is regular. Then so is the language $L' = \{0^x 1^y : x,y \ge 0 \wedge y \mid x\}$ obtained as the intersection between the complement of $L$ and $0^*1^*$.
Let $n$ be the pumping length of $L'$ and consider the word $w = 0^{n+1} 1^{n+1} \in L'$.
By the pumping lemma, there is some constant $c$ such that $1 \le c \le n$ and, for every non-...
2
I agree that the way the lemma is written is confusing, a more friendly way to write the lemma is as follows (I have added an intuitive explanation for the conditions appearing in the lemma, hoping that it is more human readable now):
The Pumping Lemma: for every regular language $L\subseteq \Sigma^*$, there is a positive pumping constant $p$ such that for ...
2
You don’t need any code. If S is any set of integers such that the difference between neighbouring elements becomes arbitrary large, then $\{a^k: k \in S\}$ is non-regular.
2
I don't see how the hint could be useful in applying the pumping lemma except from the fact that there are infinitely many prime numbers. So you start by a picking a word $w$ of the form $a^r$, where $r$ is a prime that is greater than the pumping constant. Then, think how many times you need to pump in order to get a word of the form $a^k$, where $k$ is non-...
Only top voted, non community-wiki answers of a minimum length are eligible
