Tag Info

New answers tagged

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 has $n$ 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