# Tag Info

1

You can get a double sum using inclusion-exclusion. I doubt you'll find anything closer to a closed form than that. Let $C$ be the set of $2(n-1)$ conditions of which we want the sequence to satisfy at least $m$, namely, the $n-1$ conditions that $02$ occurs at a certain position and the $n-1$ conditions that $20$ occurs at a certain position. Let $A_S$ ...

1

Here is a theoretical approach. I will slightly change your notation and take the alphabet $A = \{a,b,c\}$. Let us denote by $|u|_{ac}$ (respectively $|u|_{ca}$) the number of occurrences of the factor $ac$ (respectively $ca$) in $u$. Let $\delta: A^* \to \mathbb{N}$ the function defined by $\delta(u) = |u|_{ac} +|u|_{ca}$. Step 1. Prove that $\delta$ is a ...

3

Your first answer is now correct. Your second shows that you understand what the language is, but your notation is incorrect. $L_1$ is a set of words; your expression is not a set, and it uses the symbol $b$ both for the letter in $\Sigma$ and for the number of times it appears in a word. I would write $$L_1=\left\{a^{3m+1}b^{3n+1}:m,n\ge 0\right\}\;;$$ ...

0

The general idea to simulate two finite automata running at once, here independent counting processes with $Q_1$: $3$ states for counting digit $0$: counted $0$, $1$, $2$ or more digits $Q_2$: $4$ states for counting digit $1$: counted $0$, $1$, $2$, $3$ or more digits is to construct the product states $Q_1 \times Q_2$ and the product automaton, as ...

2

Use an automaton with the following states Have seen no 0 and no 1 Have seen one 0 and no 1 Have seen at least two 0 and no 1 Have seen no 0 and one 1 Have seen one 0 and one 1 Have seen at least two 0 and one 1 Have seen no 0 and two 1 Have seen one 0 and two 1 Have seen at least two 0 and two 1 Have seen at least three 1 with the obvious transitions ...

0

Imagine a transition table with $n$ rows, and columns with pairs (new-state, write) given read 0, (new-state, write) given read 1. There are $n^2a^2$ ways to make each row. There are $n$ rows. The total number of machines is thus $n^{n^{2}a^{2}}$. Add 1 to $a$ to account for an empty "no-write" character. When I get enough reputation points I'll post an ...

0

Let $A = \{0, 1\}$ be the alphabet and let $$L = \{yxzx^Ry^R \mid x,y,z \text{ belongs to } \{0,1\}^+ \}$$ I claim that $L$ is regular and equal to $K$, where $$K = 00A^+00 \cup 01A^+10 \cup 10A^+10 \cup 11A^+11$$ Proof. If $u \in L$, then $u = yxzx^Ry^R$ for some words $x,y,z \in A^+$. Let $v = yx$. Observing that $v^R = x^Ry^R$, we get u \in ... 2 The language is regular. It’s the union of the following four languages, each of which is clearly regular: \begin{align*} L_1=\left\{00z00:z\in\{0,1\}^+\right\}\\ L_2=\left\{11z11:z\in\{0,1\}^+\right\}\\ L_3=\left\{01z10:z\in\{0,1\}^+\right\}\\ L_4=\left\{10z01:z\in\{0,1\}^+\right\}\\ \end{align*} The problem with your pumping lemma argument is that ... 1 In general: For a general approach I don't know anything better than constructing an automaton, minimizing it, and then recalculating the equivalence classes again. However, there are a few tricks that very often speed up this process, or sometimes even make it unnecessary. Still, this works only because the automatons you usually have to deal with are ... 1 Without output The state space hasn$elements and the input space has$2$elements. The state transition function maps the possible input-state pairs into the states. There are$2n$such pairs. That is, we are talking about functions that map sets of$2n$elements onto sets of$n$elements. There are $$n^{2n}$$ such functions since any pair of input-state ... 0 For a word$w\in\{a,b\}^*$,$|w|_a$is the number of$a$s in$w$. Thus,$L_1$is the set of all strings of$a$s and$b$s having an even number of$a$s. (Note that$0$is even.)$L_2$the set of all strings of$a$s and$b$s having an even number of$a$s, an even number of$b$s, or both. In other words, the only strings of$a$s and$b$s that are not in$L_2\$ ...

Top 50 recent answers are included