Tag Info

2

$0^*$ will generate any number of repetitions of $0$, and will also generate the empty string $\epsilon$. So, the problem with your expression is that $11$ is also accepted, since we can write it as $$11=(\epsilon 1\epsilon) (\epsilon 1 \epsilon)\in (0^*10^*)(0^*10^*)\subseteq(0^*10^*)^*$$ To fix this problem, use the $0^+$ operator instead, which acts just ...

0

There is no language $L$ that has a 'unique' automaton. For this language $L$ there is however a unique minimal automaton, this is a consequence of the Myhill-Nerode theorem. From the minimal automaton for $L$ we can construct an infinite amount of different non-minimal automaton for the same language $L$ by simply adding states. If adding unreachable states ...

2

Sure. You can easily find an automaton that recognizes the language $\{a\}$, and one that recognizes the language $\{aa\}$, and one that recognizes the language $\{aaa\}$. You can probably see where I'm going from here...

4

Given the regular languages $L, L'$, based on the DFA for $L,L'$ we can: make an DFA for the complement of a language $\overline L$, and construct a DFA for the intersection $L \cap L'$. The first is done by converting all the accepting states to non-accepting and vice-versa. The second can be done by calculating the intersection of two DFA's. This gives ...

2

Here is an algorithm that should work (unfortunately, I don't know how to write a satisfactory proof): The idea is to create a bad path through the graph so that the specific word you want to remove does not end up in a final state. Care must be taken so that this path is not reachable from any other state other than the initial one (i.e. for each state in ...

3

FSA just means "finite state automaton" and it doesn't specify whether we are talking about deterministic automata or non-determinsitic automata. DFA is a shorthand for deterministic FSA. FSA and DFA can be used as synonyms if it is clear from the context that we are dealing with deterministic automata.

1

The automaton is deterministic, so any string over $\{0,1\}$ has a unique path. We need at least one $1$ to move from $q_1$ to the component where is the accepting state. Immediately after reading $1$ we are always in accepting state $q_2$. Look at the last $1$ in the input. At that moment we accept in $q_2$. To return to the accepting state, only reading $0$...

4

Not really, unless you include TMs in some way or another in the "situation". Any infinite loop in an NFA must constitute only of $\epsilon$ transitions (since the input is finite, if the loop would have "eaten up" some letters, it must also be finite). As you already know, its pretty easy to get rid of those epsilon transitions, so after ...

3

In the paper https://arxiv.org/abs/1408.5963 Thue-Morse sequence was used to construct a distributed algorithm which is non-local but halts on every finite network (input).

0

For coding test like this one :D. Using breadth first search could solve this but it soon eats up memory as pos grows large. Binary search works but Thue-Morse has the best runtime. Consider a special family of Engineers and Doctors. This family has the following rules: Everybody has two children. The first child of an Engineer is an Engineer and the ...

2

Yes, since we can let $i$ be 0. Every non-empty word $x\in L$ can be expressed as "$xx^0\epsilon$". We can also let $i$ be 1. Every non-empty word $x\in L$ can be expressed as "$\epsilon x^1\epsilon$". The statements above are rather trivial and banal. So, the real question is, given a regular language $L$, is there some $i\geq 2$ such ...

Top 50 recent answers are included