New answers tagged formal-languages
1
You are confusing the size of a set of things and the size of the things the set contains.
The empty set contains nothing. Its size (or cardinality of you want to be sesquipedalian) is 0.
A set of containing one thing has size 1. It doesn't matter whether the one thing is an elephant, a flea, or a string. If there is one thing, the cardinality is 1. That ...
0
In the Pumping Lemma (for regular languages) we consider a division $w = xyz$ for a long enough world $w$.
In the Lemma it is required that $y\neq \varepsilon$ (or equivalently $|y|> 0$). The reason is very practical. When $y=\varepsilon$ no letters are pumped, and $y^i = \varepsilon$ for all $i$, and then in fact $xy^iz = w$ belongs to $L$ for all $i$. ...
0
The pumping Lemma is very abstract, yet very obvious if you check where it comes from.
If L is a regular language then there is a finite state machine with exactly P states. If you examine a string w of P or more symbols, then after processing P symbols you must have entered the same state twice. Say the first state entered twice is X, then w = axb where ...
4
Consider a DFA for the original language with states $Q$, initial state $q_0$, final states $F$, and transition function $\delta$. We construct an NFA for the new language which operates roughly as follows:
It first guesses the initial symbol $a$.
It then reads the word $w$.
A state is accepting if $wa \in L$.
To implement this, the set of states will be $\...
-1
$S = a^Pb^{PM}c^{PM}$. It can be divided in $S = xyz$ where $x = \epsilon, y = a^P, z = b^{PM}c^{PM}$ which satisfies the following conditions:
$$ |xy| \le P $$
$$ xy^iz \in L $$
$$ |y| >= 1 $$
The middle condition is satisfied because the length of a is irrelevant to the length of b and c.
But, this doesn’t mean that a language is regular. The pumping ...
1
Im assuming the OP meant the question is $(\forall M. M \text{ is nondeterministic polynomial TM }, L(\overline{M})\in P) \iff P=NP$.
Look at Steven's answer for the solution regarding the other interpretation of this question.
This proof assumes $\overline M$ is a TM that accepts $(w, x)$ where $w$ is a witness for $x $, iff $M$ rejected $(w,x)$. This does ...
1
Let's imagine a Non Deterministic Turing Machine $M$ that decide $SAT$. If we tune this machine a bit, and add a transition on the initial state, for every letter read, that reject the entry. Let $M'$ be the new NTM. Then, $L(M') = L(M)$, since $u\in L(M) \Leftrightarrow \exists$ at least one computational path in $M$ to an accepting state (and the same ...
0
Assume m ≠ m'. After processing $0^m$ and $0^{m'}$ you cant be in the same state, because in one state adding $1^m$ is not accepted and in the other state adding $1^m$ is accepted. Since is the case for all m ≠ m', the number of states is not finite.
3
Try to express in natural language what $\overline{L}$ contains; that is, what words $L$ doesn't contain. Most obviously, it's "words of the form $0^m0^n$, with $m = n$." However, it also contains "words that are not of the form $0^m1^n$", such as "$101010$". That's why the intersection with $0^*1^*$ is employed, to not bother ...
2
Condition 3 as in the question, "$\forall i >0, \exists z= uv^iwx^iy \in L$" does not make sense. It should be "$uv^iwx^iy \in L\text{ for all } i\ge0$", i.e., $uv^0wx^0y=uwy$, $uv^1wx^1y=uvwxy$, $uv^2wx^2y$, $uv^3wx^3y$, $uv^4wx^4y$, and so on are in $L$. Please note the first word, $uwy$, where $v$ and $x$ do not appear, i.e, we &...
1
Here is an example. Consider the problem of vertex cover. An instance of vertex cover consists of a graph $G$ and an integer $k$. This is the domain $D$. You can easily come up with a one-to-one encoding $e\colon D \to \Sigma^*$ such that (i) you can recognize whether a string is in the range of $e$ in polynomial time, (ii) given such a string, you can ...
1
You seem to be looking for a deterministic procedure that isn't there.
With multiple production rules, you solve in every possible way. For instance, for the grammar
$S \rightarrow a \\ S \rightarrow aS$
we have
$
\underset{G}{S \implies a}, \\
\underset{G}{S \implies aS}, \\
\underset{G}{aS \implies aa}, \\
\underset{G}{aS \implies aaS}, \\
\ldots
$
1
You already got your answer in the comments: both the solutions provided solve the task. The only thing in which they differ is from which angle the attempt to solve the task. The author one goes from an empty set and adds only words that satisfy the given constraints (bottom-up approach). Yours goes from the set of all possible words and removes the ones ...
1
If $L$ and $\overline{L}$ were both finite, then so would $\Sigma^* = L \cup \overline{L}$ be, which we know is false.
This is a qualitative statement. We can make it quantitative by considering densities. Let us say that a language is dense if for infinitely many $n$, it contains at least half the words of length $n$. It is easy to check that at least one ...
0
If $w \in (L^R)^*$, then $w = w_1 \ldots w_\ell$ for some $w_1,\ldots,w_\ell \in L^R$. Hence $w_1^R,\ldots,w_\ell^R \in L$, and so $w_\ell^R \ldots w_1^R \in L^*$. This shows that $w = (w_\ell^R \ldots w_1^R)^R \in (L^*)^R$.
Similarly, if $w \in (L^*)^R$ then $w = x^R$ for $x \in L^*$. Since $x \in L^*$, $x = x_1 \ldots x_\ell$ for some $x_1,\ldots,x_\ell \...
-1
Your intuition is correct, however I wouldn't call it a "formal" proof. A really formal proof (but seriously, its too formal) can be stated like that:
If $L$ is infinite, we are done. Otherwise, $|L|<\infty$. In particular, there is some $w\in L$ such that $|w|\ge |w'|$ for every other $w'\in L$ - that is, $w$ is the longest in $L$. Denote $n:=|...
4
The answer depends on your standard of proof. Let's try to be very strict.
First of all, let us define words. In contrast to Peter Linz, we will not be afraid of the empty string. The set of words $\Sigma^*$ satisfies the following:
If $w \in \Sigma^*$ then either $w = \epsilon$ or $w = x\sigma$, where $x \in \Sigma^*$ and $\sigma \in \Sigma$.
$\epsilon \...
2
Consider this version of the halting problem: given $T$, decide whether $T(\varepsilon)$ halts (where $\varepsilon$ denotes the empty string).
Let $\overline{0}$ (resp. $\overline{1}$) be the string containing $101$ zeros (resp. ones) and suppose towards a contradiction that your function is computable. Then, given $T$ you can construct a Turing machine $M_T$...
2
Since for a given $n$, there are only finitely many strings in $\Sigma^n$, saying "run $M$ on all words from $\Sigma^n$" does make sense. But we need to be somewhat careful about the details here.
We could run $M$ on all $w \in \Sigma^*$ in parallel. If we do that, then (assuming that $M$ halts on at least one of them, which we may do here), there ...
2
Suppose that the longest word in the language has length $m$. The Turing machine reads the first $m+1$ symbols on the input tape. Based on that, it can decide whether the input belongs to the language or not. This Turing machine runs in constant time.
1
Look at the time hierarchy theorem for an explanation. In particular, we know (using this theorem) that $P\subsetneq E\subsetneq EXP\subsetneq R$, and we could have added a lot more complexity classes in between them.
3
Suppose that $w$ is in the language. We can write $w$ as a concatenation of runs:
$$
w = a^{i_1} b^{j_1} a^{i_2} b^{j_2} \dots a^{i_m} b^{j_m},
$$
where all indices other than possibly $i_1,j_m$ are strictly positive.
A word of this form belongs to $(a^nb^n)^m$ if all indices are equal. Since $w$ is in the language, there must exist two indices which are ...
1
You say
$\langle M \rangle$ should accept all the inputs, and if one of the inputs rejected it's not $L(M)=\Sigma^∗$.
The above two statements are true, but you are not handling all behaviors of $M$.
In particular you are not considering that $M$ could never halt on some input $x$. In that case $L(M) \neq \Sigma^*$.
In short, your observation do not imply ...
2
Indeed, $abaaabbb \notin L_1$ because the string is not of the form $(a^nb^n)^m$ which is the repetition of a fixed string with the same number of $a$ and $b$.
The language $L_2$ is the Kleene closure of $\{a^nb^n \mid n\ge1\}$, consisting of all arbitrary concatenations of strings of the form $a^nb^n$. We can choose different strings of this form, and do ...
3
Consider the intersection of your language $L$ with the regular language $L' = \{b^r a^m \mid r,m \ge 0 \}$.
Then $L \cap L'$ contains all the words of the form $a^k b^r a^m$ where $k=0$ and $m=k+r=r$. That is, $L \cap L' = \{ b^r a^r \mid r \ge 0 \}$, which is a well-known non-regular language.
1
Any word can be written as a concatenation of runs. For example,
$$ aaabbabaccbbbc = a^3b^2a^1b^1a^1c^2b^3c^1. $$
Each run is a positive power of a symbol, and the constraint is that two adjacent runs are powers of different symbols. Each word can be decomposed into runs in a unique way.
The regular expression $(a+b)^*c^*(a+b)^*$ captures all words with at ...
Top 50 recent answers are included
