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 \...
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 $\...
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 ...
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.
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 ...
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.
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 &...
2
This is a typical ambiguous grammar for arithmetic expressions. You can write different unambiguous equivalent grammars. For example, if you use the traditional precedences and associativities;
$\begin{align*}
E &\to E + T \mid E - T \mid T \\
T &\to T * F \mid T / F \mid F \\
F &\to x \mid y \mid ( E )
\end{align*}$
You could also go ...
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 ...
1
The semantic rules of the attribute grammar "compute" the value of the expression to the left in terms of the values of the expressions to the right. With a grammar for regular expressions as you propose this is straightforward, but precisely because of that this can be confusing.
For instance the meaning of the rule $S_0\to S_1 S_2$ is ...
1
Any "interesting" regular expression (i.e., one that includes Kleene star) represents an infinite set. Thus to "calculate the set of all strings" won't work so well. In a sense, the regular expression is a compact description of the language. What other kind of description do you expect to construct?
It is rather easy to construct regular ...
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 ...
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 ...
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
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 ...
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
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.
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 ...
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
