New answers tagged

1

You are technically correct. A modern practical computer has finitely many states, and so any program it runs will eventually repeat a state. However, I would like to warn against interpreting this observation in the wrong way. It is not a problem in practice. The number of possible states is huge (it's huuuuuuuuuuuuuuuuuuuuge). Algorithms that are designed ...


0

Consider the following algorithm: $n \gets 0$ repeat: $n \gets n+1$ The algorithm runs for infinitely many steps without repeating the same state.


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}...


1

Yes, as long as your alphabet is defined as a set of different couples of binary digits


1

Since FSM's can't count identical sequences, I don't think both of your answers would be correct. You can take a look here, (pumping lemma) to prove why $L= \{a^nb^n | n \ge 0 \}$ is not regular, thus you can't write a FSM for it. Also a good example here shows the proof. On the other hand it would be different if you are meaning $a^*b^*a$ which can be ...


1

$\lambda$ denotes the empty string, which is written "" in programming languages. The regular expression you give matches the empty string because you can choose each "$a+\lambda$" to match $\lambda$, and each "$(b+c)^*$" to match zero copies of $b+c$. So the expression matches, among other things, $\lambda\lambda\lambda\lambda\lambda\lambda\lambda$, ...


1

To generate an empty string you take: $(b+c)^*$ as $\epsilon$, and all the following elements which have a Kleene-star as $\epsilon$ (I will use $\epsilon$ instead of $\lambda$). Then you have: $$\epsilon(a+\epsilon)\epsilon(a+\epsilon)\epsilon$$ Which is equivalent to: $$(a+\epsilon)(a+\epsilon)$$ Which is essentially picking two options a or $\epsilon$ ...


0

If the current state is one of $a,b$, then the following state is one of $b,c$.


0

Your algorithm is incorrect. Think about the minimal DFA for $ab^*c$. Related: Do self-loops in DFA cause infinite languages?, Do all DFA's containing an "accepting path containing a cycle" accept infinite languages?.


1

Imagine an NFA with a single state, which is final/accepting. It has no edges. This NFA accepts the language $\{\varepsilon\}$—that is, only the empty string. If it is given a non-empty string, it looks for appropriate edges leading away from the starting state, finds none, and fails.


Top 50 recent answers are included