Tag Info

Hot answers tagged

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\}\;;$$ ...


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


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


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

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


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



Only top voted, non community-wiki answers of a minimum length are eligible