New answers tagged automata
0
votes
Help with understanding a stipulation in pumping lemma
Go back to how the pumping lemma is created: If L is regular then there is a state machine recognising L with p states. If you process the first n characters of a string, you must visit at least one ...
- 25.9k
0
votes
Help with understanding a stipulation in pumping lemma
If $p$ is the pumping length of your language $L$, the pumping lemma guarantees that $w = 0^p 1 1 0^p$ can be decomposed as $xyz$ with $|xy| \le p$, $|y| \ge 1$, and $xy^iz \in L$ for all integers $i \...
- 24.2k
0
votes
Proof for Language: L1 ∪ L2 ⊆ L1L2
To prove $L_1 \cup L_2 \subseteq L_1L_2$
you prove that $\forall x. (x\in L_1 \cup L_2) \rightarrow(x\in L_1L_2)$
To prove that, you prove that
$\forall x. (x\in L_1) \rightarrow(x\in L_1L_2)$
and
$\...
- 1,254
2
votes
Accepted
Suppose we have an empty alphabet Σ=∅, what are the possible languages of this alphabet?
Actually your list of properties already solves the problem. As $\varepsilon$ is an element of $\Sigma^*$ and we cannot have any longer word due to the lack of symbols, we have $\varnothing^*=\{\...
- 28.2k
4
votes
Accepted
pumping lemma length restrictions clarification
First, for the sake of preciseness, note that the Lemma says that for every regular language $L$, there exists a constant $m\ge 1$, such that for every word $w\in L$... [what you wrote]. That is, the ...
- 16.5k
2
votes
Free description of the Kameda-Weiner algorithm?
Here is a succinct but somewhat abstract description of the technique based on [1]. Also reading [2] to understand the universal automaton before approaching this description is recommended.
I am also ...
1
vote
How to recognize all halting states of a turing machine?
A turing machine is defined as a 7-tuple $M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle$. The set $F$ in the tuple is the set of final states or accepting states. So any other states other ...
- 170
2
votes
Accepted
Describing the Language of a DFA with 7 States
To accept a string, you must start in $q_0$ and end in $q_0$ or in $q_3$.
A path from $q_0$ to $q_0$ can make a cycle through $q_5$ (so you can have $(ba)^*$) or through $q_1,q_2,q_3,q_4$ (and so $a(...
- 835
2
votes
Accepted
Meaning of lambda-transitions in npda
Usually, the first symbol means what you expect to read from the input (1), the second what is the symbol at the top of the stack (2) and the third what will happen with the stack (3).
$\lambda$ or $\...
- 246
Top 50 recent answers are included