4
The regular expression is correct.
You can use a trie-like structure, i.e.
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'...
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.)
...
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\}$
...
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 ...
1
If $L$ were regular than so would the following language be:
$$L \cap ca^*b^* = \{ ca^nb^n \mid n \geq 0 \}.$$
You can show that the latter language is not regular in various ways.
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.
Only top voted, non community-wiki answers of a minimum length are eligible
