New answers tagged

1

Your construction starts with a CFG $G$ in Greibach normal form. So each of the productions of $G$ is of the form $A \to a \alpha$, with $A$ nonterminal, $a$ terminal and $\alpha$ a string of nonterminals. Such a production is then directly translated into a PDA instruction $(q,a,A) \mapsto (q,\alpha)$. "read $a$ from the tape, pop $A$ and push $\alpha$" In ...


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


0

There is a more economical solution for DFAs. Suppose that $\langle Q,\Sigma,q_0,\delta,F \rangle$ is a DFA for $L$. We construct a DFA $\langle Q', \Sigma', q'_0, \delta',F' \rangle$ for $L_1$ as follows: $Q' = Q \times \{0,1\} \cup \{ q_{\mathit{sink}} \}$. $q'_0 = \langle q_0, 0 \rangle$. If $\delta(q,\sigma) \in F$ then $\delta'(\langle q,0 \rangle, \...


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


3

PDAs that are allowed to have more than one initial state (let's call them PDAIs) are computationally equivalent to conventional PDAs: Trivially, every conventional PDA can be considered as a PDAI that happens to have one initial state. Every PDAI can be converted to an equivalent PDA with the process you describe. So yes, PDAIs accept exactly the context ...


1

Yes this is possible. In fact, if we take out the non-determinism from the PDAs, then we end up with something that is computationally significantly weaker!


2

Try constructing an NFA for $\hat L:=\{w|$ there is an odd length prefix of $w$ that is $\notin L\}$, given a DFA for $\overline L$, and then show $L_1=\overline {\hat L} $. If I'm not mistaken, this should work out.


1

A "language" is a set of words over a finite alphabet $\Sigma$ to define a language we have to make an extra step. Take the following definitions s $$L_0 = \{\}$$ $$L_1 = \Sigma$$ $$L_{n+1} = \{(c, w) \mid c \in \Sigma \land w \in L_n\}$$ Note that $(c, w)$ is usually denoted simply as $cw$ or $c \cdot w$ but for the sake of not introducing notation I chose ...


1

It means for every context free language there is an algorithm that can correctly decide if any string S is in the language or not. We can actually say something a lot stronger: There is actually a known algorithm that can take an arbitrary context free language and a string as input and decide in polynomial time whether the string is in the language.


0

Wikipedia is using $\cup$ in its usual meaning, set union. When Wikipedia defines $$ V^* = \bigcup_{n \geq 0} V^n = V^0 \cup V^1 \cup V^2 \cup \cdots, $$ it literally means that $V^*$ is the union of the sets $V^0,V^1,V^2,\ldots$ The concatenation happens in the definition of $V^n$, which can be defined as follows: $V^0 = \{\epsilon\}$, and $V^{n+1} = \{ ...


2

Automata theory is rarely used by practicing programmers today. It is in principle useful for building compilers and parsers (though most developers don't need to do that today, and often use tools to help them). Some of the concepts can be useful for building state-machine based systems, which are widespread (including, e.g., embedded systems), though it'...


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

Take the language L and an DFA for it. For any two states $S_i$ and $S_j$, we can determine all the lengths of strings that would go from $S_i$ to $S_j$: To get there, we will have single character transitions, and loops, and in any case the possible lengths will be of the form ak + b for fixed a ≥ 1 and 0 ≤ b < a and k ≥ $k_0$, plus various lengths < $...


1

(I think by pointers you mean the "pebbles" that are described in Kozen's Automata and Computability.) The language $L'$ is regular. You can prove that as follows: Consider the DFA $D_1 = (Q, \delta, F, q_0)$ for $L$. We will create another automata $D_2 = (Q \times Q \times Q \times \{0,1\}, \Delta_2, F_2, I)$. $I = \{(q_0, q, q, 0) : q,q_0 \in Q\}$ ...


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.


1

Yes $K$ is a regular language. Lets try to see this using closure properties of regular languages. Consider the marked duplicate alphabet of $\Sigma$, $\Sigma' = \{ a' | a \in \Sigma \} $. Now consider the homomorphisms $\alpha, \beta, \gamma$ defined as follows. $$ \alpha : \Sigma \cup \Sigma' \mapsto \Sigma$$ $$ \alpha(a) = a $$ $$\alpha(a') = a$$ $$ \...


1

The most direct method to solve the problem is to show to build, starting with finite state automata $A_L$ and $A_M$ for the regular languages $L,M$, a new automaton for the new language $K$ which is constructed from $L$ and $M$. For this you need an idea, a formal construction, and (if you are not convinced) a proof the construction is correct. The idea ...


4

The regular expression is correct. You can use a trie-like structure, i.e.


Top 50 recent answers are included