Tag Info

New answers tagged

0

Hint. As you said, your FSM has five states, $0$, $1$, $2$, $3$, $4$, corresponding to the possible values of $(x_1 \dotsm x_t)$ modulo $5$. As you observed, if the next bit is $0$, then the value of the number doubles, and if the next bit is $1$, then the value of the number is obtained by doubling and adding $1$. Therefore, for each state $q$, you have ...


1

It is just a variation on Hagen von Eitzen's answer. Let $S$ be your language and let $f: A^* \to \mathbb{N}$ be the monoid morphism defined by $f(u)= |u|$, where $|u|$ denotes the length of $u$. If $S$ is regular, then $f(S)$ is a rational subset of $\mathbb{N}$, that is, a finite union of arithmetic progressions. But $f(S)$ is the set of Fibonacci numbers ...


1

Idea behind the pumping lemma: $L$ is a regular language, thus $L$ can be recognized by a finite automaton. Such automaton has only a finite number of states. Recognition paths must traverse those states, thus for large words (with a length equal or greater than a critical length $p$) repetition must occur along the recognition path and thus within the ...


0

For your example of decimal strings divisible by $6$, consider the residue modulo $6$ of what has been read as the state $q$; adding a new digit $d$ gives state $(10 q + d) \bmod 6$, which is easy to compute. Might need to spice up with a starting state to avoid strings starting with $0$, and make the state $0$ accepting. This can obviously be generalized to ...


5

If the language is regular, then the pumping lemma guarantees that the set of lengths contains an arithmetic subsequence. But the lengths of valid strings are the Fibonacci numbers, which grow exponentially.


1

The answer is unfortunately negative. You are trying to determine some language $L$. If you just know that a finite set of words $F$ is contained in $L$ and that another finite set of words $G$ (disjoint from $F$) is contained in the complement of $L$, then $L$ could be any language of the form $F \cup H$, where $H \cap G = \emptyset$. Thus this information ...


2

I think that since you’re just beginning, it would be best to include the dead state in your graphical description of the automaton. (Indeed, some instructors will require you to do so.) You need to include it in the full symbolic description anyway, and the automaton is so simple that including it in the graph doesn’t really add any clutter: even with the ...


0

Muller automata. A path $\pi$ is accepting if $Inf(\pi) \in \mathcal{F}$. This is equivalent to saying that there exists $F \in \mathcal{F}$ such that $Inf(\pi) = F$. In the logical setting, this condition should be written as $Inf(\pi)$ exactly satisfies $Acc$, where $Acc$ is an appropriate formula. Thus $Acc$ can be written as $\bigvee_{F \in ...


0

This may not be quite what you're looking for, but graph dynamical systems apply dynamical systems theory to automata theory. Particularly, cellular automata. There is a book on this: http://www.amazon.com/Introduction-Sequential-Dynamical-Systems-Universitext/dp/0387306544 Much of the research in this field comes from the Network Dynamics and Simulation ...


0

Consider that if you define disjoint alphabets for $R_1$ and $R_2$, then, given regular expressions for the languages $R_1$ and $R_2$, all you need to do is concatenate the two regular expressions for $R_1$ and $R_2$ (using their different alphabets) and then, because they use different alphabets, you can tell for each string in this bizarre regular ...


3

Let $A = R_{1}$ and $B = R_{2}$. Let $M(A)$ and $M(B)$ be the finite state machines accepting $A$ and $B$ respectively. Define $M(A \times B)$ to be the machine with states $Q_{A} \times Q_{B}$, transition function $\delta_{A} \times \delta_{B}$ and final states $F_{A} \times F_{B}$. Argue that this machine captures $A \times B$ exactly. Without loss of ...


0

Given language is "empty language".We have to construct a finite automata for this language.In general we consider "the construction of finite automata" as "the construction of DFA".So....{Let us assume input symbol as 'a' and 'b'} (a)If we take one state(initial state) and don't show any transition of any input symbol over this state,then this structure ...


1

Short answer. This is a consequence of the fact that regular languages are closed under left and right quotients by any language. Given languages $L$, $X$ and $Y$ of $A^*$, let $$ X^{-1}LY^{-1} = \{u \in A^* \mid \text{there exist $x \in X$ and $y \in Y$ such that $xuy \in L$}\} $$ I let you verify that $(X^{-1}L)Y^{-1} = X^{-1}(LY^{-1}) = X^{-1}LY^{-1}$ so ...


1

We can proceed by induction on the regularity of the language. There are $5$ cases to consider: The empty language. Well, in this case, the infixes would also constitute the empty language, which is regular. A singleton language. The infixes would constitute just the singleton language again, so we're done here. If the empty string is allowed, then we're ...


2

Finite state automata passes from one state into another, depending on the symbols it encounters on it's input, until it finally arrives in one of it's two terminal states, accepting or rejecting the input string. But along the way, it can keep track of symbols it previously encountered by encoding information about that in it's present state. For example, I ...


2

Finite Automaton can only be in one state at a time.It can not store any input string/symbols,due to unavailability of storage space. When finite automaton read an input signal it can only do two things either accept the input and transition to another state or final state or reject the input . Finite automaton which say accepts all the strings that end ...



Top 50 recent answers are included