# Tag Info

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