# Tag Info

3

Let $A = R_{1}$ and $B = R_{2}$. Let $M(A)$ and $M(B)$ be the finite state machines accepting $A$ and $B$ respectively. Define $M(A \times B)$ to be the machine with states $Q_{A} \times Q_{B}$, transition function $\delta_{A} \times \delta_{B}$ and final states $F_{A} \times F_{B}$. Argue that this machine captures $A \times B$ exactly. Without loss of ...

2

Let $A = \{a,b\}$. The following languages are star-fee (in order of difficulty) Every finite language, $a^*$ $(ab)^*$ $(ab,ba)^*$ $(a(ab)^*)b^*$ $(a(a(ab)^*)b^*)b^*$ More generally, the languages $D_n$ defined by $D_0 = 1$ and $D_{n+1} = (aD_nb)^*$. You could also use the following result of [2] to build other examples. A submonoid $M$ of $A^*$ is pure ...

2

This is either trivial or hugely difficult, depending on exactly what it means to "represent" a language "as math". In both directions it seems like you should know more about this than we do. I mean as I type this various English words are being represented as sequences of integers inside this machine - is that "representing" English "as math"? On the ...

1

Short answer. This is a consequence of the fact that regular languages are closed under left and right quotients by any language. Given languages $L$, $X$ and $Y$ of $A^*$, let $$X^{-1}LY^{-1} = \{u \in A^* \mid \text{there exist x \in X and y \in Y such that xuy \in L}\}$$ I let you verify that $(X^{-1}L)Y^{-1} = X^{-1}(LY^{-1}) = X^{-1}LY^{-1}$ so ...

1

We can proceed by induction on the regularity of the language. There are $5$ cases to consider: The empty language. Well, in this case, the infixes would also constitute the empty language, which is regular. A singleton language. The infixes would constitute just the singleton language again, so we're done here. If the empty string is allowed, then we're ...

1

The key is to decompose the condition $mn \geqslant 3$. It means either ($m = 1$ and $n \geqslant 3$) or ($m = 2$ and $n \geqslant 2$) or ($m \geqslant 3$ and $n \geqslant 1$). Thus your language can be written as $01^31^* \cup 0^21^21^* \cup 0^30^*11^*$.

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