New answers tagged formal-languages
-1
PDA:
Here is a guideline to solve this problem:
Try to think how to "count the letters until the middle", then "guess" where the middle is, and then "verify that your guess was really the middle, by counting once again"
CFG:
$S\rightarrow b\space | \space xSy$ for every $x,y\in \{a,b\}$
Yea, thats everything in the CFG!
1
Your construction starts with a CFG $G$ in Greibach normal form. So each of the productions of $G$ is of the form $A \to a \alpha$, with $A$ nonterminal, $a$ terminal and $\alpha$ a string of nonterminals. Such a production is then directly translated into a PDA instruction $(q,a,A) \mapsto (q,\alpha)$. "read $a$ from the tape, pop $A$ and push $\alpha$"
In ...
1
You can write this language as
$$
\{ a^k b^m a^m a^\ell a^k \mid k,m,\ell \in \mathbb{N} \}.
$$
This description easily lends itself to conversion into a context-free grammar.
0
Yes, since "the first, the middle, and the last characters of $w$ are identical" is not really well defined here (so there might be ambiguities like is $\epsilon\in L$?)
Probably it wont really matter for the question if you assume $\epsilon\in L$ or $\epsilon \notin L$ (other than some small change in the PDA or CFG) But if you really want to make sure ...
0
I recommend to use this explanation on how to transform a CFG into a (1 state) PDA
1
You can easily transform this grammar to LL(1) by extracting the common prefix $b$ in both productions of $B$, a procedure called left-factoring.
You get this:
$B \to b B'$
$B' \to B c$
$B' \to c$
Then $B$ always starts with $b$ and $B'$ starts either with $b$ or with $c$ which can be desided by looking at only one input symbol.
1
Using the definitions from: Theoretical Computer Science: Introduction to Automata and Computability by Juraj Hromkovič.
A representation for the graph will be said to be Unambiguous if the graph can be reconstructed from that representation.
Basically, we wish to encode a general graph using boolean alphabet $\Sigma = \{0,1\}$. If we had an additional ...
3
All three notions are related to variables. You can think of variables as named placeholders for some expression.
When introducing/declaring a new variable, you create a placeholder for an abstract expression (abstract in the sense that the variable does not represent a particular expression). Every variable declaration creates also a scope for that ...
0
There is a more economical solution for DFAs.
Suppose that $\langle Q,\Sigma,q_0,\delta,F \rangle$ is a DFA for $L$. We construct a DFA $\langle Q', \Sigma', q'_0, \delta',F' \rangle$ for $L_1$ as follows:
$Q' = Q \times \{0,1\} \cup \{ q_{\mathit{sink}} \}$.
$q'_0 = \langle q_0, 0 \rangle$.
If $\delta(q,\sigma) \in F$ then $\delta'(\langle q,0 \rangle, \...
2
First, there's a typo at your definition of $\hat\delta$. Case $\hat\delta(q,\alpha x)$ should be $\bigcup_{p_i \in \hat\delta(q,\alpha)}ECLOSURE(\delta(\color{green}{p_i},x))$ (green for highlighting the difference).
The equivalent definition in terms of a string given as $(x\alpha)$, where $x\in\Sigma$ and $\alpha\in\Sigma^*$, is
$$
\hat\delta(q,x\alpha) =...
0
To show $w\in L(G_{Pal})$, Show with induction on word length the lemma: "If $w=w^R$ then $P\rightarrow...\rightarrow w$"
basis is simple. Do it yourself.
assume $|w|=n+1$ and we know that every $\hat w$ with $\hat w = \hat w^R, |\hat w|\le n$ satisfies, $P\rightarrow...\rightarrow \hat w.$ Then:
define $\hat w:=w_{2,...,n}$. since $w=w^R$ then also $\hat w ...
3
PDAs that are allowed to have more than one initial state (let's call them PDAIs) are computationally equivalent to conventional PDAs:
Trivially, every conventional PDA can be considered as a PDAI that happens to have one initial state.
Every PDAI can be converted to an equivalent PDA with the process you describe.
So yes, PDAIs accept exactly the context ...
1
Yes this is possible. In fact, if we take out the non-determinism from the PDAs, then we end up with something that is computationally significantly weaker!
2
Try constructing an NFA for $\hat L:=\{w|$ there is an odd length prefix of $w$ that is $\notin L\}$, given a DFA for $\overline L$, and then show $L_1=\overline {\hat L} $.
If I'm not mistaken, this should work out.
0
Define C = { $L | L$ is decidable by a turing machine with at most 42 states }
Notice that there is a finite amount of such languages, as there are a finite amount of turing machines with 42 states. for that reason, we have $C\ne\emptyset, \sum^*$
By Rice's theorem, the language $S=$ { $w | L(M_w) \in C$ } is undecidable. This language is precisely the ...
0
There are two cases:
$L$ is empty. In this case, $L' = \emptyset$ is trivially decidable.
$L$ is non-empty. Let $m$ be the minimum length of a word in $L$. Then $L'$ consists of all words of length at least $m$, and is again trivially decidable (in constant time!).
As you can see, you never actually need an algorithm for $L$.
Similarly, the following ...
1
The set partition problem asks whether there exists a 2-partition of a multi-set such that sum of numbers in one set is equal to the sum of numbers in the other set.
Note the phrase whether there exists; if you are already being given the partition in the input $\langle S,A,B \rangle$ then the problem becomes whether the given partition is valid and sum of ...
3
A language over $\{0\}$ is any subset of the set S of all strings consisting of a finite number of 0s. S is countable, the set of all subsets of S is uncountable.
Any decidable language must be decided by some algorithm. The set of algorithms, no matter how you describe it, is countable, not uncountable. Therefore some subsets of S (actually almost all) ...
1
Hint: let $A$ be a NP-complete language and $B=\Sigma^*$. Then $A \cup B = \Sigma^*$. Is $B$ the complement of $A$? Does it belong to coNPC?
2
No. Consider any undecidable language $L$ (for example, take the language $Halt = \{(M,x): \text{ M halts on x}\}$), we can encode each string of this language in unary (by writing the binary number representing $(M,x)$ in unary using $0$ as the symbol) to get a language $L_0 \subseteq \{0\}^*$. It’s not hard to see that $L_0$ will also be undecidable ...
0
If co-$A$ is decidable then so is $A$, as you mention in your question.
However the mere fact that $A \le_m$ co-$A$ does not imply the dependability of $A$. See this answer.
0
Wikipedia is using $\cup$ in its usual meaning, set union. When Wikipedia defines
$$
V^* = \bigcup_{n \geq 0} V^n = V^0 \cup V^1 \cup V^2 \cup \cdots,
$$
it literally means that $V^*$ is the union of the sets $V^0,V^1,V^2,\ldots$
The concatenation happens in the definition of $V^n$, which can be defined as follows: $V^0 = \{\epsilon\}$, and $V^{n+1} = \{ ...
3
This follows from the pumping lemma, if you examine the proof closely enough.
2
The idea is to start generating the ones of the first addend from the axiom $S$, while simultaneously adding the corresponding number of ones at the end of the sentential form. Then you have a production from $S$ to non-terminal $A$ which takes care of generating the second added, while still appending ones at the end of the sentential form.
When you are ...
0
Yes, it is possible. Enumerate the set of all possible Turing machines and let $H$ (resp. $\overline{H}$) be the set indices of Turing machines that halt (resp. do not halt) on empty input.
Let $L = \{ \langle T, 1 \rangle \, : T \in H \} \cup \{ \langle T, 0 \rangle \, : T \in \overline{H} \}$.
Clearly $L$ is not decidable but it is possible to reduce $L$ ...
1
Suppose towards a contradiction that $L$ is context-free and let $c$ be the pumping length of $L$.
Consider the word $a^{c^2} b^c$ which, by the pumping lemma, can be written as $uvwxy$ with $1 \le |vx| \le c$.
Notice that:
$vx$ cannot contain only $b$s, since otherwise $uwy \not\in L$.
$vx$ cannot contain only $a$s, since otherwise $uv^2wx^2y \not\in L$....
0
I didn't try to minimize your particular automaton but it is definitely possible for a minimal DFA to have a dead state. Keep in mind that often such states are omitted from the graphical representation of the automaton (nevertheless they are still part of the set of states of the DFA).
Think, for example, of a minimal DFA that recognizes $L=\{a\}$ over the ...
3
I'll just show how to build a grammar for $L_1 = \{ u\#v, |u|_a > |v|_a \}$. Then it'll be straightforward to combine 4 similar grammars into a grammar for $L$.
The idea is to write $u\#v$ as $xay\#v$ with $x,y,v \in \{a,b\}^*$ and $|y|_a = |v|_a$. The construction of $y\#v$ is handled by the non-terminal $Z$ which "grows" it from the center.
$$
\...
1
Yes. Actually, it is even true that for every language $L_1$ there is a language $L_2 \supseteq L_1$ such that $L_2$ is regular.
Proof: Pick $L_2 = \Sigma^*. \square$
2
$$L_1 = \{a^{n+1}b^{2n}a^{n+1} \mid n \ge 0\}$$
$$L_2 = \{w \mid (\#_a(w) + \#_b(w)) \bmod 2 = 1\}$$
I assume that $\#_a(w)$ means the number of $a$s in $w$.
First, I would write out some $w$ in $L_1$ and $L_2$:
$$L_1 = \{aa, aabbaa, aaabbbbaaa, \ldots\}$$
$$L_2 = \{a, b, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaaa, \ldots\}$$
From this, we see that ...
0
This is not a CFL. We can prove this using pumping lemma for CFL.
We prove it as follows: Consider the string $s = 0^n1^n0^n\#0^n1^n0^n \in L$. By pumping lemma, for a significantly large $n$, we can split the string in five parts: $u,v,w,x,y$ such that $s = uvwxy$, $|vx| > 0$, and $uv^mwx^my \in L$ for all $m$.
Basically, you have to find out two ...
1
There is an interesting language that is $\Theta({loglog(n)})$, I found it in the free google book preview of the book "Turing Machines with Sublogarithmic Space", Here is the language:
$C = \{a^n|F(n)\text{ is a power of 2}\}$
$F(n)=\min\{i|i\text{ does not divide n}\}$
It is $\Theta(\log\log(n))$ because of the following construction of an accepting ...
1
Consider the word $w = 0^n1^n0^n \# 0^n1^n0^n \in L$ for a sufficiently large value of $n$.
By the pumping lemma for context-free languages, we know that if $L$ is context-free then there are$a,b,c,d,e = \Sigma^*$, with $|bcd| < n$ and $|bd|>1$ such that $w=abcde$ and, for every $i \ge 0$, $a b^i c d^i e\in L$.
Notice that neither $b$ nor $d$ can ...
1
Every language of this form can be represented as a regular expression without nested Kleene star. That is, its star height is $1$. The star height hierarchy is strict, and in particular, it is known that the language $(a^*b^*c)^*$ cannot be represented in that form. An example over a binary alphabet would be $(aa(ab)^*bb(ab)^*)^*$.
0
This is the FOLLOW function:
$follow(S) = \{\$,+,-,b,],c\}$
$follow(X) = \{],c\}$
$follow(Y) = \{b,],c\}$
1
Yes $K$ is a regular language. Lets try to see this using closure properties of regular languages. Consider the marked duplicate alphabet of $\Sigma$, $\Sigma' = \{ a' | a \in \Sigma \} $.
Now consider the homomorphisms $\alpha, \beta, \gamma$ defined as follows.
$$ \alpha : \Sigma \cup \Sigma' \mapsto \Sigma$$ $$ \alpha(a) = a $$ $$\alpha(a') = a$$
$$ \...
1
The most direct method to solve the problem is to show to build, starting with finite state automata $A_L$ and $A_M$ for the regular languages $L,M$, a new automaton for the new language $K$ which is constructed from $L$ and $M$.
For this you need an idea, a formal construction, and (if you are not convinced) a proof the construction is correct.
The idea ...
0
We can write every string in $\{0,1\}^*$ in the form
$$
0^{i_0} 1 0^{i_1} 1 0^{i_2} \cdots 0^{i_{m-1}} 1 0^{i_m}
$$
Here $i_j \geq 0$, and $m$ is the number of $1$s.
The number of copies of $001$ is the number of indices $i_0,\ldots,i_{m-1}$ which are at least $2$.
The number of copies of $100$ is the number of indices $i_1,\ldots,i_m$ which are at least $...
0
$L=\{\epsilon, 0, 1, 01, 10, 010, 101, 00, 000, 0000,..... , 1, 11, 11111,......, 01110, 1001, 00100,.........\}$
The pattern I can observe here is whenever we see a '001' as a substring then it has to be followed by 00 to make $n(001)=n(100)$ and whenever we see '100' as a substring then it has to be followed by 1 to make it '1001' to make $n(100)=n(001)$
0
There are basically two possible types of derivations:
Ones that start $S \to^* X^naY^n$.
Ones that start $S \to^* X^nbY^n$.
Derivations of the first type will produce $a^{2n+1}$, those of the second type will produce $b^{n+1} a^n$.
Top 50 recent answers are included
