# Tag Info

13

You are indeed allowed to have unreachable states in DFAs (or NFAs, or various other automata models). You may wonder what is the point of having them, given that they are unreachable and have no effect on the language. Well, automata are typically not designed by hand. Rather, they are usually obtained algorithmically by translation from other types of ...

8

Check the definition. It usually goes like $M = (Q, \Sigma, \delta, q_0, F)$, with $Q$ a finite set of states, $\Sigma$ the (input) alphabet, $\delta \colon Q \times \Sigma \to Q$ the transition function, $q_0 \in Q$ the initial state, $F \subseteq Q$ the set of final (accepting) states. Note that the only condition on $\delta$ is it being a function. To ...

3

Your proof that the problem is in PSPACE is not quite correct. The problem is that the product $n_1 \cdots n_k$ is not bounded by a polynomial in the input length $n_1 + \dots + n_k$. The correct way to do it is to directly apply Savitch's theorem to the NPSPACE machine that nondeterministically guesses a path through the product graph. The difference is ...

2

Yes, this is (kind of) correct, in the following sense: The set of languages that can be recognized by Turing Machines with a fixed tape is equivalent to the set of regular languages (i.e. the set of languages recognizable by finite automata). The reason behind this is that such Turing Machines have a finite number of configurations, which is independent ...

2

The problem is PSPACE-complete, by reduction from the equivalence problem for NFAs. Suppose we are given two NFAs $A_1,A_2$ over an alphabet $\Sigma$. Let $\dashv$ be a new symbol. To each of the NFAs we add two new states $q_f,q_t$, and the following transitions: An $\epsilon$-transition from the initial state to $q_t$. A self-loop on $q_t$ labeled $\... 2 If you know how to construct DFAs for two languages separately, you can use systematic methods to build the DFA which recognises the intersection of the languages (e.g. https://math.stackexchange.com/questions/147457/intersection-of-two-deterministic-finite-automata). However to achieve a minimalist and elegant result (as well as for learning purposes) you ... 2 There are many ways to perform this enumeration. Note first that you can count the number of cases in half by postulating that$Q = \{q_0,q_1\}$, that is, fixing which among the two states is initial; the choice doesn't matter due to symmetry. Now you are left with 16 possibilities. At this point there are many ways to cut the search space even further. Here ... 2 Yes, your understanding on point 2 is correct. Your understanding on point 3 is mostly correct, except where you say "mark final state as explained in 1st bullet point in point 1". That statement doesn't type-check, as you can't do that to the$\epsilon$-NFA. If you've created an$\epsilon$-NFA, then its states are of the form$S_1$or$S_2$(where$S_1$... 2 Let$M$be a DFA for the language$L$and let$M_1$and$M_2$be$M$with two different collections of some number$m$of unreachable states added.$M_1$and$M_2$both have the same number of states and both accept$L$, but they need not be isomorphic. For a less trivial example, consider the following two DFAs: Start state: 1 Accepting states: 2, 4 1 -a-&... 1 As Rick Decker rightly noted, real-world lexical analysers produce a DFA with multiple final states. Lexical analysers created via Lex-like generators differ from theoretical DFAs in several respects, and this is only one of them. Another obvious difference is that they don't stop at the end of the input string. Instead, lexical analyser generators ... 1 This is a DFA for binary numbers divisible by three. your desirable language is reverse of this language. For reversion of language of a DFA, you must reverse all of its transitions and change its initial state with its final state. in this case initial and final states are same, also its language is symmetric so all of transitions are symmetric. Therefore ... 1 Yup, It does behave like a finite state machine. if for (every permutation in tape string, every current head position, every next move) you create a unique state, you are besically creating a DFA like mechanism, as (next move/tape write) is determined by those variables and you have a state for every possible combination. And as the tape is finite, the no ... 1$L_1\circ L_2$can certainly still be non-regular. For example, when$L_1$contains exactly one word. However,$L_1\circ L_2$can be regular, too. Here is an example. Let$L_1=\{\epsilon,0\}$. Let$L_2$be the complement of$\{ 0^n1^n \mid n \gt 0 \}$. As the complement of a non-regular language,$L_2$is not regular while$L_1\circ L_2\$, the set of all ...

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