# Tag Info

0

Hint. Your language is the union of two (regular) languages: the langage $L_1$ of all words containing an even number of $1$'s and the language $L_2$ of the words of length multiple of 3. Now just find a regular expression for $L_1$ and a regular expression for $L_2$ (this is easy in both cases) and just take the union of your two regular expressions.

0

I think in the even number of $1$'s category, your NFA will miss strings of the form $110$ since you do not have an ending $0*$ at the end of your regex. The other part of your regex only detects strings of length $3$, not multiples of 3. The correct thing would be to allow the second part of your regex to be repeated as many times as you want. So, doing ...

0

Here is a possible NFA for the language $1(0 + 0(10)^*0)0$:

0

I think you can add a branch in second 0-transitions to take a union operation. It is feasible in NFA. Here is a required NFA.

0

The key idea, which you mentioned, is to show that this problem is equivalent to the halting problem (on a single input). Suppose you had a decider $D$ for the 3-input problem, and use this to get a decider for the usual halting problem. Since we know that the halting problem is undecidable, our assumption must have been wrong and there is no such $D$.

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

0

At that point you know that the string $$a_1\ldots a_n\underbrace{00\ldots 00}_{i-1\text{ zeroes}}\tag{1}$$ is a string of length $n+i-1$ that has a $1$ in position $i$, while $$b_1\ldots b_n\underbrace{00\ldots 00}_{i-1\text{ zeroes}}\tag{2}$$ is a string of length $n+i-1$ that has a $0$ in position $i$. There are $$(n+i-1)-i=n-1$$ bits after $a_i$ ...

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

0

Let $M_0$ and $M_1$ be two copies of a DFA for $L$, and let $M$ be their disjoint union. The initial state of $M_0$ will be the initial state of $M$. Replace each transition $p\overset{x}\longrightarrow q$ of $M_0$ by an $\epsilon$-transition $p\overset{\epsilon}\longrightarrow q'$, where $q'$ is the copy of $q$ in $M_1$. Replace each transition ...

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 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 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. 0 The question doesn't make sense: the n in LL(n) is a property of a language not a grammar. An LL(n) language is one that can be parsed by an LL parser that uses at most n look-ahead tokens. So any LL(1) language is LL(2) (because a parser can just ignore the second look-ahead token). 0 The definition translates directly into the regular expression [ab]*c?[ab]* | [abc]*[bc][abc] (That is, there's either at most one c, or the penultimate symbol is not an a.) This can be turned directly into a DFA using regular expression derivatives. I came up with a DFA with 12 states, from which the minimal seven-state DFA can easily be computed: Here ... 0 Corrected HINT: Everything matching the regular expression$$b^*+ab^*+aab^*+aaaaa^*+(a+b)^*ba(a+b)^*\tag{1}$$is in the complement of L, and it’s easy to write a grammar for this part of the complement. Every string in the rest of the complement begins with aaa, contains at least one b, and does not contain the string ba, so it must be a^nb^m ... 0 DFA to RE conversion can be done systematically, using what is essentially linear algebra. For each i, let L_i be the language of words starting in state s_i and ending in an accept state. The DFA gives us the following system of "linear equations" in the L_i's:$$\begin{eqnarray} L_0 &=& b L_1 + a L_2\\ L_1 &=& a L_1 + b L_2 + ...

0

$L$ is finite, so it’s certainly regular: it consists of all $7$-letter words over $\{a,b\}$ that contain exactly $3$ $a$s and $4$ $b$s. There are $\binom73=35$ such words. One regular expression for the language simply lists all $35$ of these words in a long disjunction: $$aaabbbb+aababbb+aabbabbb+\ldots+bbbbaaa\;.$$ $L'$ is still regular: a word is in ...

0

This question will help you. You have to solve the system of equations under the monoid $(\Sigma, \circ, \epsilon)$ : $$\begin{cases} \Xi_0 = 0 \Xi_1 \cup 1 \Xi_2 \\ \Xi_1 = 0 \Xi_0 \cup 1 \Xi_2 \\ \Xi_2 = (0 \cup 1) \Xi_2 \cup \left\{\epsilon \right\} \end{cases}$$ for $\Xi_0$.

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, ... 0 Since you asked for clarification on how to approach the design of the Turing machine, I'm not going to solve the problem, but just present a design process that I use. I am also not completely sure what that notation is trying to get across, whether it is strings of the form 001, 000011, etc, or strings of the form #(0000,11). As these are only different in ... 0 HINT: The first thing to note is that a character$[abc]$can be a valid input if and only if$a+b=c$,$a+b=10+c$,$a+b+1=c$, or$a+b+1=10+c$(i.e.,$a+b=9+c$). The first two of these are valid if there is no carry from the previous input; the last two are valid if there is such a carry. The second and fourth generate a carry, and the first and ... 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. ... 0 There are two possible definitions of a deterministic automaton, depending on whether you consider complete automata or allow incomplete ones. An automaton is complete deterministic if it has exactly one initial state and, for every state$p$and for every letter$a$, there is exactly one state$q$such that$p \xrightarrow{a} q$is a transition. An ... 0 The number of transitions a node has isn't what makes it deterministic. What makes a automata nondeterministic is if a state more then one transitions for the same input. In your second diagram$q_1$has two transitions labelled with '1'. While in your first diagram every state every transition coming out of a node has a different label. 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 ... 0 Let$L$be the recognized language of the Büchi automaton and$L_X$the language described in part$X$.$L_C$is contained in$L$. Every word in$L$has to be accepted along a path which contains the finial state infinite many times. The final state can only be assumed by recognizing a$1$symbol. So$L$is contained in$L_C$too and$L = L_C$follows. ... 2 The correct answer is C. Regardless of what state it is currently in, the automaton moves to the initial state on reading a$0$or$2$and to the acceptor state on reading a$1$. Thus, it is in the acceptor state infinitely many times while reading the word if and only if the word has infinitely many$1$s. The sets described in A and D are proper subsets of ... 0 the simplest way is that define NFA with states like$q_{ijk}$where$i,j,k \in \{0,1,2,3,n \}$that$i$determine the number of$a$and$j$determine the number of$b$and$k$determine the number of$c$. when an index is$n$means its greater than$3$. you can easly define function of NFA as when read$a$just from$q_{ijk}$goto$q_{i+1jk}$and if$i=n\$ ...

1

In regular expressions it would be: [bc]*a[bc]*a[bc]*a[bc]* (logical or with its versions with b and c, left as exercise for the reader) https://regex101.com/r/mI5dM4/1 (Only the 3 a version, and include \b for word boundary) It matches any (possibly empty) sequence of non-'a' characters, exactly 3 times interrupted by an 'a'.

Top 50 recent answers are included