New answers tagged

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