New answers tagged

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 $\...

Top 50 recent answers are included