New answers tagged formal-languages
0
If it was i + j >= k: You first produce a’s and c’s in pairs, then b’s and c’s in pairs, then some more b’s. But it’s i + j >= 2k, so you need 2 a’s and b’s for every c.
To do this we start producing two a’s and one c in pairs. Then we can add a single a and are done. Or we optionally add ab and c, then bb and c in pairs, then more single b’s. In ...
0
Formally, the version of
$\{ w ∈ \mathbf{\{0,1\}}^* \mid w \text{ contains at least three 1s} \}$
does not really say anything about the alphabet of the language. It might be {0,1}, but might also be bigger. Only the (part of the) alphabet, from which the desired strings are constructed is specified.
So while the language specified is the same, its ...
0
Maybe your grammar for the equality in the condition looks something like this (only the productions):
$$ S\rightarrow aS'c | aB'c, \ \ B' \rightarrow bB |b, \ \ S' \rightarrow aS | aB, \ \ B \rightarrow bB'c $$
This supposes that $i$ and $j$ must be at least one. The primed nonterminals say that we have an odd $(i+j)$, the nonprimed ones say that this ...
0
Most likely the CFG you made has some transition to an accepting state when it sees the stack is empty.
This is exactly what checks the equality between $i+j$ and $2k$.
If, instead, you would change the transition so that it will always do this transition (Notice, this is a nondeterministic PDA!), then the PDA will accept any word that reaches this state ...
0
The prefix language of $L$ is the set of all prefixes of strings in $L$, $\{w\mid \exists v \in \Sigma^*, wv\in L\}$. In other words, it is the right quotient of $L$ with $\Sigma^*$, so it is certainly regular if $L$ is regular, by closure with right quotient.
A possibly simpler way to see this is to observe that you can construct a recogniser for the prefix ...
1
A transition in a PDA always needs to read a symbol in the stack. If there is no symbol, there is no transition.
Since the PDA is deterministic, reading $w$ will always reach a configuration with an empty stack, and no transition can permit to read any non empty word.
1
You can actually do it in at most $n+1$ queries. Just first check that the whole sentence is satisfiable, then play guess-and-check for each variable. Writing $|\phi|$ for the number of variables in the sentence $\phi$,
$$\mathit{cnf\_and\_sat}(\phi)=\left\{\begin{align*}
&\mathit{cnf}(\phi,|\phi|)&\mathit{sat}(\phi)\\
&\mathbf{unsat}&\mathrm{...
1
First of all, check whether $\phi$ is satisfiable using $M$. If it is, you can find a satysying assignment as follows:
For each variable $x$ of $\phi$ do the following:
Set $x$ to true. Simplify $\phi$ to remove $x$ (if a clause contains $x$ then you can delete the clause, if a clause contains $\overline{x}$ then you can delete $\overline{x}$ from the ...
1
If you want to decide whether a CNF formula is satisfiable or not you can simply decide it with one invoke of $M$ on your formula.
But if you want to calculate its satisfying assignment, your problem is a search problem not a decision problem. To do that you can simply invoke $M$ on $\phi [True/x_i]$ (substituting variable $x_i$ with value $True$) for each ...
0
Yes; as others have said, the empty language $\varnothing$ is recognizable, and it's a subset of every language.
For a less trivial example, let $L$ be an unrecognizable language. Pick any finite subset of strings $D$ from $L$. That subset $D$ is a recognizable language—in fact, it's a regular language! The algorithm that recognizes it is a lookup table ...
0
Yes, you can simulate several TMs on separate tapes and mark a separate tape with a 1 whenever one of your simulations halts. For TMs that are well behaved (like deciders), this approach will work and your approach will answer Yes correctly.
The immediate problem is that some TMs don't behave nicely—they will run forever without halting. No matter how many ...
1
If $L$ is regular, then so is $L\{b\}^5$. You can conclude by studying $L\{b\}^5$ (which is a very classic language).
Also in your proof, you cannot guarantee that $j+k < p$, but $j+k < 5 + p$ is enough.
-1
I was also struggling with this problem. I think I might have found an ambiguous DCFG G = ({S,T,A},{a,u,v},R,S), where R is defined as
S -> ATa | aTa
T -> uv
A -> a
G is ambiguous because there are two different leftmost derivations for string auva.
S => ATa => aTa => auva
S => aTa => auva
However, G is also a DCFG because there is ...
4
The set $\Sigma^*$ is an infinite set (you can build a bijection between the naturals and the words in $\Sigma^*$ if you wish to prove this, or you can observe that, for every $k \in \mathbb{N}$, $\Sigma^*$ contains at least one word of length $k$).
Let $L$ be a finite language and suppose towards a contradiction that $\overline{L} = \Sigma^* \setminus L$ is ...
2
Here is a formal proof for the statement (warning, this really is a formal proof, and hence is not very intuitive):
Let $\Sigma$ be a non-empty alphabet (either finite or infinite), and let $L\subset \Sigma^*$, with $|L|\in \mathbb{N}$ ($L$ is finite).
Let $\alpha \in \Sigma$. By definition of the klenee-star operator, we can construct a function $g:\mathbb{...
-1
Lets denote $n:=|L|\in \mathbb{N}$.
For any nonempty $\Sigma$, it is clear that $\Sigma^*$ is infinite.
By definition, $\bar L = \Sigma^*\setminus L$. Therefore, $|\bar L| = |\Sigma^*\setminus L| = |\Sigma^*|-|L| = \infty - n=\infty$.
It is not a formal proof (neither a valid one), but it should suffice for you as intuition to understand why $\bar L$ is ...
3
"$\lambda$" is commonly used to represent the empty string, although "$\epsilon$" could be the more common one.
This was introduced earlier in that book, section "3.1 Grammar Editing" of chapter "Regular Grammars".
On the last row you will enter the production $A \rightarrow \lambda$, a
$\lambda$-production. To do ...
2
Others have already suggested the simplest and most elegant ways to prove that the diagonal language is not empty.
Indeed, we can proceed by contradiction, and argue that if the diagonal language were empty, it would be recursive, but we know it is not. Or, more constructively, if we take any TM that recognizes the empty language, then it does not accept any ...
10
Here is a simple direct proof that $L_{\text{diag}}$ is not empty.
Let $N$ be a Turing machine that does not accept any word. For example, a Turing machine that just loops forever. Suppose $N$ is encoded as the $j$-th machine. Then $L_{\text{diag}}$ contains the word $w_j$. Hence $L$ is not empty.
3
Since the diagonal language is not computable but the empty language is computable, that means that those languages are different.
1
In short your assumption: "I think q0, q1 and q2 all are final states." is true.
Suppose your $\epsilon-\text{NFA}$ is called $M_1$ and its equivalent $\text{NFA}$ is called $M_2$. every state in $M_1$ that can see at least one final state by only getting input $\epsilon$, will be a final state in $\text{NFA}$.
I think the reason will be quite ...
0
In the powerset construction $2^{\mathcal{A}}$ of an automaton $\mathcal{A}$, the final states of $2^{\mathcal{A}}$ are the sets that contain a final state of $\mathcal{A}$.
This also works when removing $\varepsilon$-transitions.
0
The pumping length here is what you refer to with the variable $n$. (Usually but not always, the letter $p$ is used, but the name is not important as long as it is clear to you and your audience.)
The meaning of the pumping length $n$ is that for a language to have the pumping property, we only require that strings of at least $n$ characters have the ...
Top 50 recent answers are included