New answers tagged

0

Start with a 3SAT instance $\phi$ on $n$ variables with $m$ clauses $C_1,\ldots,C_m$. For each clause $C_j$, we construct an NFA $A_j$ which reads a binary input string, interpreting its first $n$ symbols as encoding a truth assignment, and checks whether the clause is satisfied. If $C_j$ is satisfied, then on the $(n+1)$'th symbol it branches to $n$ new ...


0

Use the pumping lemma: If $L$ is regular, there is a constant $N \ge 1$ such that any string $\sigma \in L$ can be divided as $\sigma =\alpha \beta \gamma$ with $\lvert \alpha \beta \rvert \le N$, $\beta \ne \varepsilon$ so that for all $k$ the string $\alpha \beta^k \gamma \in L$. Proof is by contradiction. Assume your $L$ is regular, let $N$ be the lemma's ...


1

This can also be proved easily using Myhill-Nerode theorem. Myhill-Nerode Theorem: Given a language $ L \subseteq \Sigma^* $, Suppose $$ \forall x,y \in S, (x \neq y) \wedge (\exists z \in \Sigma^* ,L(xz) \neq L(yz)) $$ where S is an infinite set. Then L is not a regular language. (Here $L(w) = 1$ if $w \in L$ and $L(w) = 0$ if $w \notin L$.) For the ...


1

For $\sigma \in \Sigma$, let $f_\sigma$ be the indicator function of $L_{\epsilon,\sigma}$, let $f$ be the indicator function of $L$, and let $b$ be the indicator of $\epsilon \in L$. If $w = \sigma_1 \ldots \sigma_n$ then $$ f(w) = f_{\sigma_1}(\sigma_2 \ldots \sigma_n) \oplus f_{\sigma_2}(\sigma_3 \ldots \sigma_n) \oplus \cdots \oplus f_{\sigma_n}(\epsilon)...


0

The language $L$ is not regular. One might think $L$ is regular as it is tempting to think that the number of 010s and the number of 101s in a word are dependent. Yet, as explained by @gnasher729, this is not the case because occurrences of 010 and 101 can be far from each other. It is a bit challenging to prove non-regularity of $L$ using the pumping lemma ...


0

A string is accepted by an NFA if there is a sequence of moves such that it can reach a final state at the end of the string. As you said, assume that for $w=0110$ after reading $011$ we are in a final state (called $q$) and there is no transition like $\delta(q,0)$, this is when we encounter a situation called dead configuration. At this point we can't just ...


1

What she actually describing is the following construction. For an $\epsilon$-NFA $ A = \langle Q, \Sigma, \delta, Q_0, F \rangle$, the intuitive idea is as follows. Consider a state $q$. If there is an $\epsilon$-transition from q to $s$, then whenever we reach q, we can also reach $s$. Yet, there may be $\epsilon$-transitions from $s$, so we also need to ...


0

An epsilon transition (also epsilon move or lambda transition) allows an automaton to change its state spontaneously, i.e. without consuming an input symbol. You need them for two cases $1.$ The string or part of the string includes a Kleene star $^*$. E.g. $(10)^*$ $2.$ We have the option to choose between different strings. E.g. $0|1$ Now to make the ...


2

If $L_0$ in a context-free language, this doesn't guarantee that its complement is context free. For example, consider the language $$L_0 = \{a,b,c\}^* \setminus \{a^nb^nc^n : n \geq 0\}.$$ This language is context-free, but is complement (with respect to $\{a,b,c\}$) is not. Another way to formulate your question is as follows: given a context-free grammar ...


6

Bader Abu Radi is right. In short, there are unfortunately competing definitions used by different people on this matter: According to the most common definition, the YouTube video is right: the missing transition for strings starting with b means that the top machine is an NFA, and not a DFA. But the Automaton simulator you used has a different definition,...


8

Some people in the literature (very few actually) do not consider missing transitions as nondeterminism, and given a DFA, they allow themselves to remove all transitions that lead to states from which we cannot reach an accepting state. The reason for that is technical, as sometimes it may simplify proofs a bit. Or it could be a matter of taste. Intuitively, ...


1

The language of an automaton is the language accepted by the automaton, that is, the set of words accepted by the automaton. Now, certainly, one way of describing the language is as the language accepted by this particular automaton. But the question is asking you to find a simpler description. Here is the set of words accepted by your automaton: $$ 01, \\ ...


0

When it comes up to deciding if a language is context-free or not, I try the following 'roadmap' to come up with an answer. $1.$ Try to make a CFG for the given language. If we can make a CFG, we have proved that the language is context-free. $2.$ If step $1$ did not work out, there is a probabilty that the language is not context-free. So try proving that ...


Top 50 recent answers are included