New answers tagged formal-languages
0
Suppose that $L$ is context-free. Then the pumping lemma for context-free languages tells us that $L$ has a pumping length $p \ge 1$. We want to show that this leads to a contradiction, by exhibiting a string that is in $L$ but cannot be pumped in the manner specified in the lemma.
Consider the string $s = a^pb^pc^{(p^2)}$. Clearly, $s \in L$.
Now, see if ...
1
Let us start with an automaton for ${2^rc^r}$ for the alphabet $\{2, c\}$. This is quite a standard example. As long as you are reading $2$ add a letter to the stack until you read the first $c$. Then for each $c$ pop a letter from the stack. The word and the stack should finish at the same time.
Now using this automaton we should be able to build one for ...
0
Suppose we can find $G’$ - a grammar with the fewest variables and equivalent to $G$ - with the help of a Turing machine $T$.
Thus there exists $T$ taking input $G$ and giving output $G’$. Suppose that $G’$ is unique up to relabeling of variables.
Then we can use this $T$ to decide ${EQ_{CFG}}^1$ ; i.e. by applying $T$ on $G_1$ and on $G_2$ and deciding if ...
2
This is not a valid proof.
You ask for the intuitive reasoning that makes this proof valid, but there's no amount of intuitive reasoning you can add to make it valid. It's just simply not a good proof. It's not a matter of adding intuition; there is no rescuing it.
A valid proof starts with facts that are known to be true; then each derives a new fact ...
1
They are incomparable.
Every $LR(0)$ language has the prefix property (no sentence is a prefix of another sentence). But many $LL(k)$ languages don't have this property ($a^*$, for example).
The language $\{a^nb^mc\mid n\ge m\ge 0\}$ is $LR(0)$ but is not $LL(k)$ for any $k$.
0
Let $L \neq \emptyset$ be a language over some alphabet $\Sigma$, let $|$ be a symbol not in $\Sigma$, and consider the language $|L = \{ |w : w \in L \}$. Suppose that $L$ could be generated using a context-free grammar with a single nonterminal $S$.
Since $L \neq \emptyset$, $S \Rightarrow^* |w$ for some word $w$. Therefore:
Every rule contains at most ...
2
Suppose $R = Q + RP$, where $\epsilon \notin P$.
Let us first prove by induction that $QP^i \subseteq R$ for all $i \geq 0$. The base case $Q \subseteq R$ is clear. Now suppose that we know that $QP^i \subseteq R$. Then $QP^{i+1} \subseteq RP \subseteq R$.
Since $QP^i \subseteq R$ for all $i \geq 0$, it follows that $QP^* \subseteq R$.
Conversely, let us ...
2
There is no interesting relation between a programming language (the set of words which are syntactically valid programs) and the set of words that are accepted by a program written in said programming language.
Note that it is possible to design a Turing powerful programming language which, as a formal language, is the set $1^* = \{\epsilon,1,11,111,\ldots\...
0
Your manipulation where you went from $Q_1 = (b \cup ab)Q_2 \cup aaQ_1$ to $Q_1 = (aa)^*(b \cup ab)Q_2$ was not valid. Instead, in this case I suggest that you first start by finding a nice form for $Q_2$, before trying to manipulate $Q_1$.
A good way to handle $Q_2$ is to note that $Q_2 = a Q_2 \cup b Q_2 \cup \epsilon$ implies $Q_2 = (a \cup b) Q_2 \cup \...
0
Here is a simpler proof. We will show that for every $\ell$, the equivalence relation $\equiv_L$ has at least $\ell$ equivalence classes.
Given $\ell$, find $n$ such that $3^{n+1} - 3^n \geq \ell$. Consider the $3^{n+1} - 3^n$ words $a^0,a^1,\ldots,a^{3^{n+1}-1-3^n}$. I claim that they are pairwise inequivalent. Indeed, suppose $0 \leq i < j \leq 3^{n+1}...
0
Note that every string in $\{a,b,c\}^*$ starts with a string from $L$ (even if in some cases that string is the empty string, with $n$=0).
If a string is not in $L$ then the prefix $a^nb^nc^n$ (for largest possible $n$) is followed by a non-empty suffix.
1
First note that strings in $L= \{a^ib^jc^k: i=j=k\ge 0\}$ have a specific order and specific count of the symbols. The complement of $L$ (denoted as $L'$) then includes every string over the alphabet $\{a,b,c\}$ that does not satisfy the order and/or the count constraints. This implies that $L'$ consists of the following languages over the alphabet $A=\{a,b,...
4
How to prove the set of powers of 2 in ternary representation to be non-regular using pumping lemma?
This answer is a simpler version of Colin McQuillan's answer to the same question.
Suppose the language is regular. The pumping lemma gives strings $u,v,w$ such that every string $x_n=u v^n w$ is
a power of $2$.
Interpreting these strings as numbers and writing $d$ and $e$ for the lengths of $v$ and $w$ respectively, we have
$$
x_n = u 3^{dn+e} + v 3^{d(...
2
Your question is very philosophical in nature because you are asking about what is considered by computation and it’s physical implementations. In short, there is a ongoing discussion on different accounts of concrete computation e.g. the simple mapping account, the semantic account, the syntactic account, the mechanistic account, the causal, the ...
1
You are right in saying that the binary representation of the language is regular because it is defined by the expression $10^*$(regular expression).
You are also right in saying that this does not hold for the ternary representation.
You can prove the latter in various ways including the "calssic" pumping lemma (quite cumbersome in this case) or using ...
1
Let $L$ be a unary context-free language. According to the pumping lemma, there is a constant $p$ such that if $a^n \in L$ then either $n < p$ or there exists $q \in \{1,\ldots,p\}$ such that $a^{n+tq} \in L$ for all $t \geq 0$ (actually, the pumping lemma gives $t \geq -1$). Let $L_0$ be the set of words in $L$ of length smaller than $p$, and for $q \in \...
1
If the language is infinite, the word $\# w_1 \# w_2 \ldots$ would be infinite, and so doesn't map to an integer in any meaningful way.
Applying the diagonal argument on the set of all finite languages might (indeed, will) result in an infinite language.
1
I see two flaws in this proof sketch, one related to CFLs vs CFGs, and another related to nested quantifiers and running time as a function of multiple parameters.
Any time you have a high-level proof strategy that seems to lead to surprising results, it is a good idea to check it carefully by expanding each step to obtain a detailed proof. Expand each ...
3
I think you have to be more careful in the inductive steps, but it seems you basically have the argumentation ready. According to me proper induction would be
If $R_1$ and $R_2$ can be written as sum of products, then so can
$R_1\cdot R_2$, $R_1+R_2$ and $R_1^*$.
The proof could be completed as:
If $R_1$ and $R_2$ can be represented as sum of products ...
0
Using contradiction suppose $L=\{\left< M_1,M_2 \right>|L(M_1)\subset L(M_2)\}$ is semi-decidable. So there exists Turing machine $T$ which for input $\left<M_1,M_2\right>$ if $L(M_1)\subset L(M_2)$ will halt and accept.
We should use this Turing machine $T$ to make another Turing machine $T'$ which halt and accept on input $\left<w,M\right&...
0
This language is not CFL.
Consider the language $L \cap a^*b^*c^*$ . Assume that $L$ is CFL, now, as $ a^*b^*c^*$ is regular and CFL are closed under intersection with regular languages, $L \cap a^*b^*c^*$ would be CFL. But $L \cap a^*b^*c^* = a^nb^nc^{2n}$, which is not context free (The proof is similar to this). Hence the contradiction!
Thus the given ...
0
You can give a proof of such a property by reasoning with sets and using the definition of inverse mappings. In case of inverse morphism you can you the basic definition of inverse mappings
$x\in \varphi^{-1}(K)$ iff $\varphi(x) \in K$
This will help you with 2: $x\in \varphi^{-1}(L_1\cup L_2)$ iff $\varphi(x) \in (L_1\cup L_2)$.
Now use the property of ...
1
In both languages, each string must have twice as many $a$'s as $b$'s. For a string to be in the first language, it must satisfy the additional condition that all the $a$'s occur before any of the $b$'s. So $aba$ does not belong to the first language and does belong to the second language.
1
Your proof is incorrect because it is possible in some cases for $UVVW$ to belong to $L$. For example, take $x = [000,001,010]$ and $V =,00$. Then $UVVW = [000,00,001,010]$ whose binary strings are unique.
Here is proof that $L$ is not regular. By way of contradiction, suppose there exists a DFA $M$ with $p$ states that recognizes $L$. Consider the $p+...
1
The usual definition is that $n_a(w)$ refers to the number of $a$s in $w$.
Based on this definition, $L_1$ consists exactly of words that begin with an even number of $a$s followed by half as many $b$s (no $c$s are permitted). Therefore, you have $\varepsilon, aab, aaaabb, aaaaaabbb,... \in L_1$.
Whereas $L_2$ consists of words containing an even number of ...
2
Now if we have $UVVW$ that means $V$ is repeating some of the characters in $x$ and therefore it must repeat some $x_i$. Therefore we have reached a contradiction, which shows that $L$ is not a regular language.
This is not necessarily true. Suppose $x=[0^p, 0^{p-1}, \dots, 00, 0]$. If $V$ is of length $k<p$ and entirely in $0^p$, we get $UVVW = [0^{p+k},...
1
Your proof doesn't quite work because of the last step: "Now if we have $UVVW$ that means $V$ is repeating some of the characters in $x$ and therefore it must repeat some $x_i$."
The problem with this is that the substring being pumped is not necessarily an entire $x_i$. It could be the middle of an $x_i$, which would not necessarily invalidate the string's ...
0
Q1: A state can get repeated. The point is that if a state gets repeated and no non-empty symbol has even been written, then you known the that the Turing machine will never halt as it is necessarily stuck cycling through some of the states encountered so far. Since none of the states of the cycle caused the TM to write a non-blank symbol, the TM will never ...
3
All sources agree on the definition of right quotient: $L_1/L_2$ is the set of words which can be extended by a word in $L_2$ to become a word in $L_1$. In other words, $w \in L_1/L_2$ if there exists $x \in L_2$ such that $wx \in L_1$.
If $L_1$ is regular and $L_2$ is any language then $L_1/L_2$ is regular.
For many classes of languages, if $L_1$ belongs ...
2
Whether a word and its extensions belongs to $L_n$ or not depends on its final $n$ letters (we'll see later what happens if a word is shorter than $n$ letters). Indeed, we can "probe" all of these letters using the following: for $i=1,\ldots,n$, we have $w1^{n-i} \in L_n$ iff the $i$th letter from the end is $1$. This shows that if two words have different ...
0
So I feel the definitions of universal language differs in both
sources. Q1. Right?
You quoted Ullman's definition for Universal language but didn't quoted the other source definition of universal language. The other source defined universal Turing machine which is not language. So the answer to your first question is that no you aren't right since the ...
0
So first Q1:
At first the definitions of universal language and the universal machine.
The universal language is defined as you mentioned in the question:
$$ U= \{(M,w)\:|\:\text( TM\:M\:accepts\:w)\} $$
The Universal Turing Machine on the other hand is defined as follows:
A machine, which can simulate an arbitrary TM on arbitrary input. Or you can say: ...
5
There is no known natural example of such a pair, and indeed there are various results in computability theory suggesting that such a pair does not exist. So to whip up an example one has to do some work.
The simplest approach (indeed, the easiest I know) is via mutual diagonalization: we build inductively a pair of increasing sequences of infinite binary ...
3
It appears that $prefix(L)$ is non-regular.
Let $L = \{0^n 1^n: n \ge 0\}$. Then, $prefix(L)$, defined to be the set of all prefixes of strings in $L$, is the set of all strings that consist of zero or more $0$'s followed by at most the same number of $1$'s, i.e. $prefix(L) = \{0^n 1^m: m \le n\}$. Intuitively, the reason $prefix(L)$ is nonregular is that ...
0
$$
\begin{align*}
S \to & AbBC \mid AbBCc \mid AbBCcc \; \mid \\
& aAbBC \mid aAbBCc \mid aAbbBCcc \; \mid \\
& aaAbBC \mid aaAbbBCc \mid aaAbbBCcc \\
B \to & bB \mid \epsilon \\
A \to & aaaAb \mid \epsilon \\
C \to & bCccc \mid \epsilon
\end{align*}
$$
The intuition is as follows:
The nonterminal $B$ encodes the fact that we ...
0
Rice theorem can be applied when we are talking about languages of Turing machines, not about Turing machine behavior or characteristics themselves or anything else which is not related to "only" languages they accept.
You are talking about a narrow Rice's theorem. In Wikipedia, it states that
Rice's theorem can also be put in terms of functions: for ...
0
You're right that both of these are non-trivial properties. The key is, Rice's theorem applies only to non-trivial semantic properties.
So what defines a semantic property?
Intuitively, a "semantic" property is a property of what the machine does, rather than how the machine works. If you treat the machine as a black box that takes input and gives output, ...
4
You said in a comment:
I am talking to process this encoding, not the tape content.
But the tape content affects the behavior of the TM, including whether it would enter an accepting state. The exact same TM in the exact same state might later accept, or not accept, depending only on what is on the tape.
You want to "go through all encoded transitions ...
2
Because this process doesn't necessarily end; you can end up discovering more and more possible configurations (state+tape) which would lead to accepting if they were ever reached, but never a legal initial configuration.
Top 50 recent answers are included
