Tag Info

Hot answers tagged

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


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


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


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



Only top voted, non community-wiki answers of a minimum length are eligible