Hot answers tagged

1

You are correct in thinking that $L_1$ is not even context-free, though the reason that you give is not a proof; it’s not too hard to find a proof using the pumping lemma for context-free languages, however, and it’s even easier to prove that $L_1$ is not regular using the pumping lemma for regular languages. It’s true that $L_1\subseteq L_1/L_2$, for the ...


1

No. The empty language $\emptyset$ is regular and for every language $L$, $\emptyset L = \emptyset$ is also regular. This does not imply that $L$ is regular. Edit. To answer your comment, here is another counterexample. Let $A$ be the alphabet. Then, for every language $L$ containing the empty word, $A^*L = A^*$. This does not imply that $L$ is regular.


1

Indeed, there is an elegant way to compute this. The process of finding the language accepted by an automaton $A = (Q,\Sigma, \delta, q_0, F)$ involves solving a system of equations over the monoid $(\Sigma, \circ, \epsilon)$ with $\epsilon$ denoting the empty word of the alphabet. Denote as $\Xi_i$ the language recognized by the automaton $(Q, \Sigma, ...


1

You essentially need two copies of the (00010 + 1101 + 1010) automaton to distinguish the parity, i.e., we need to keep track of the overall parity as well as the 0-1-sequence since the last completed $(00010+1101+1010)^\star$ (fortunately, there is always only one way to reach every valid string): Thus create nodes carrying mnemonic labels: even, odd0, ...


1

HINT: I think that it’s at least as easy to construct a DFA directly. Since every DFA is in fact an NFA as well, this does not violate the letter of the instructions, though it may violate their spirit. Let $L_0$ be the set of words over $\Sigma=\{a,b,c\}$ whose lengths are divisible by $4$, and let $$L_1=\left\{w\in\Sigma^*:|w|_a+|w|_b\text{ is ...


1

There are two major problems that prevent your argument from working. First, you're completely missing that a Turing machine is not the same as a DFA. DFAs are much weaker than Turing machine, but in your construction you seem to be assuming that you can feed an arbitrary Turing machine into $T$, which is only assumed to work when its input is a DFA. ...


1

I can't answer all of your questions, but I can tell you how I would attempt to do it. a + bi is made from 3 components, real numbers (a, b), operators (+) and the imaginary symbol (i). So we need to be able to express all 3. + and i are easy, it's just the symbol themselves. So onto a real number, we can either write its decimal expansion (4.2) or with ...


1

The state removal method is probably the simplest to do by hand. In this example, we need only remove one state, $2$. Afterward, the edge $0\to1$ will be labeled $a\mid bb$, the edge $1\to0$ will be labeled $b\mid aa$, and we add loops $0\to 0$ labeled $(ba)^*$ and $1\to1$ labeled $(ab)^*$. The resulting regular expression is $$(ba)^*(a\mid ...



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