New answers tagged

3

This is wrong. Determinization of an NFA with $r$ states could result in a DFA with up to $2^r$ states. Therefore your argument actually gives an upper bound of $$2^{nm}. $$ This can be improved if you switch the order of operations. If you first convert your NFA to a DFA and only then apply the product construction, then you get the better bound $$ n2^m. $$ ...


0

Take two inputs x and y, and for each one find the shortest non-empty string $a^k$ such that adding $a^k$ ends up in an accepting state. If for x and y these strings are different, then x and y must reach different states. If there are infinitely many x and y such that these strings are different, then the language cannot be regular. Let x = $a^p$ for a ...


1

Since languages $A$ and $B$ are regular, we can assume there are DFAs $$ M_A = \{Q_A, \Sigma, \delta_A, s_A, F_A\} ~~\text{and}~~ M_B = \{Q_B, \Sigma, \delta_B, s_B, F_B\} $$ that recognize them, respectively. Let's call the zig-zag lanuage $Z$. It is easy to see that the alphabet of $Z$ is $\Sigma$. We will construct a DFA, $M_Z = \{Q_Z, \Sigma, \delta_Z, ...


0

You can think of it as of a correct implementation of an algorithm in different programming languages. No matter which implementation you choose they all do exactly the same thing described by the algorithm. Regular expressions or deterministic finite automata are just two different "programming languages" for implementing a regular language. If an ...


0

It means the automaton recognizes exactly it. in fact, you can even build an automaton that accepts every word (try to do it yourself), so there would be no meaning in the other definition


1

let $Q=Q_A\times Q_B\times \{1,2\}$ (1 means A, 2 means B) also define $F=F_A\times F_B\times \{2\}$ (we end with B) and $q_0=(q_A,q_B,1)$ (we start with A) with the delta function: $\delta ((q_1,q_2, i),\sigma)= \begin{cases} (\delta(q_1,\sigma),q_2,2) &i=1 \\ (q_1, \delta(q_2,\sigma),1) &i=2 \end{cases}$ The idea is to ...


2

First, there's a typo at your definition of $\hat\delta$. Case $\hat\delta(q,\alpha x)$ should be $\bigcup_{p_i \in \hat\delta(q,\alpha)}ECLOSURE(\delta(\color{green}{p_i},x))$ (green for highlighting the difference). The equivalent definition in terms of a string given as $(x\alpha)$, where $x\in\Sigma$ and $\alpha\in\Sigma^*$, is $$ \hat\delta(q,x\alpha) =...


0

To show $w\in L(G_{Pal})$, Show with induction on word length the lemma: "If $w=w^R$ then $P\rightarrow...\rightarrow w$" basis is simple. Do it yourself. assume $|w|=n+1$ and we know that every $\hat w$ with $\hat w = \hat w^R, |\hat w|\le n$ satisfies, $P\rightarrow...\rightarrow \hat w.$ Then: define $\hat w:=w_{2,...,n}$. since $w=w^R$ then also $\hat w ...


0

There seems to be nothing better than enumerating all 32 strings, because of the connection between first and last, 2nd and 9th character etc.


1

From the theoretical perspective: there is a completely algorithmic procedure that given a DFA returns an equivalent DFA with the minimum number of states. In your specific case: remove the $\epsilon$ transition and merge state $2$ with state $5$.


1

Simply remove state 2, and make a transition from 1 to 5 directly. This will get rid both of a state (state 2) and a connection (the epsilon connection)


0

A deterministic finite automaton is a tuple $\langle Q,\Sigma,q_0,\delta,F \rangle$, where $Q$ is a finite set ("states"), $\Sigma$ is a finite non-empty set ("alphabet"), $q_0$ is an element of $Q$ ("initial state"), $\delta$ is a function from $Q,\Sigma$ to $Q$ ("transition function"), and $F$ is a subset of $Q$ ("accepting states"). (Your definition ...


4

This is not an union of two regular languages! It's a concatenation. Note the difference, Union: $L_1 \cup L_2$ Concatenation: $\{ab : a \in L_1 \wedge b \in L_2\}$. That said, your other observations are correct, and indeed the concatenation of two regular languages is also regular itself. You can prove this by constructing two NFAs for the regular ...


1

Sticking $w$ with its reverse together usually is not a regular language and therefore there is no natural concise way to represent that using regular expressions (at least to my knowledge) Im not really sure why you would like to find a regular expression for this language, since - as you have stated - this language is finite, and therefore regular (if you ...


2

The problem is to find a DFA, such that the only two words it accepts are '$\epsilon$' - the empty word, and '0'


1

Yes, this is allowed (and in fact, you lose a lot of computational power without it) here is a definition of DFA (both formal and as drawings) + an example


0

Suppose you have a Turing machine with an $n$ sized tape with $k$ symbols and $s$ states. This system, as a whole, then has $s\cdot k^n \cdot n$ possible states it can be in ($s$ states, $k^n$ tape contents, $n$ tape head positions). By definition $k$ and $s$ must be $O(1)$. If $n$ also is however, then the entire expression $s \cdot k^n \cdot n$ is a ...


2

Yes, we can transform an epsilon NFA into a NFA by keeping the same state set, basically adding new edges. If there is an $\varepsilon$ path from state $p$ to state $q$, and an edge from state $q$ to state $r$, then add an $a$ edge from $p$ to $r$. Also, if from state $p$ we can reach a final state then state $p$ can be made accepting. After these two steps ...


1

This is obviously not correct, as every state is an accepting state - meaning this will accept literally every word (not to mention you forgot to define what B does when it sees a '1'). Although, even if we would have changed state A to be non-accepting, then this dfa would have accepted words with exactly one 1's (and any amount of 0's) To fix this, we ...


3

This dfa is incorrect. To start, a dfa MUST define a transition for every node, including accepting nodes. Anyhow, the current dfa would have accepted the language L = { w | w is a series of 1's and a single 0 at the end } To correct this, you need to add another transition from B to A when it recieves 1 and a transition from B to itself when recieving 0. ...


2

Your language $L$ is not regular. Suppose that it was regular, then its complement $\overline{L}$ is also regular and the intersection $M = \{ a^j,b^k \mid j=k \vee j \not\equiv k \pmod{3} \}$ between $\overline{L}$ and $\{a^j,b^k \mid j,k \ge 0\}$ is regular. Let $n$ a sufficiently large multiple of $3$ and consider the word $a^n b^n$. By the pumping ...


2

Recursively break down your regular expression into elementary sub-expressions. In you case you can write your expression $E=b(a^*dc)^*$ as the concatenation of $b$ with $(a^*dc)^*$. In turn $(a^*dc)^*$ is the Kleene closure of $a^*dc$ which can be broken down as $a^*$ and $dc$. Finally $a^*$ is the Kleene closure of $a$. You can construct your NFA from ...


0

I didn't try to minimize your particular automaton but it is definitely possible for a minimal DFA to have a dead state. Keep in mind that often such states are omitted from the graphical representation of the automaton (nevertheless they are still part of the set of states of the DFA). Think, for example, of a minimal DFA that recognizes $L=\{a\}$ over the ...


1

Here is a simpler example, for NFAs. We will show that if $L_1,L_2$ are regular languages over disjoint alphabets $\Sigma_1,\Sigma_2$, then so is the following language over $\Sigma = \Sigma_1 \cup \Sigma_2$: $$ L = \{ xyz : x,z \in \Sigma_1^*, y \in \Sigma_2^*, xz \in L_1, y \in L_2 \}. $$ Here is the idea. Start with DFAs $A_1,A_2$ for $L_1,L_2$. We will ...


1

Yes, a state can go to itself when seeing any symbol. (As Steven's answer says, the analogous question for head movement - whether the head of the Turing machine has to move at each stage, or whether it can stay put at a given moment - varies from definition to definition, but I've never seen a definition which prohibits a state from looping to itself.) ...


0

That depends on the exact definition of Turing Machine that you are using. I am used to a definition where the transition function $\delta$ is a function from $(Q \setminus F)$ to $Q \times \Sigma \times M$, where $Q$ is the set of all states, $F$ is the set of final states, $\Sigma$ is the tape alphabet, and $M=\{\text{left, right, stay}\}$ specifies the ...


0

Add a new state and make the self loop point to the new state and add a empty transition from the new state back to the original state. It is straightforward to prove that this NFA is equivalent to the original.


Top 50 recent answers are included