Tag Info

Hot answers tagged

4

Denote by $s(L)$ the number of states of the minimal (deterministic) automaton of a regular language $L$. The following result is proved in [1]. Let $A$ be a two letter alphabet and let $$ f(n) = \max \{s(L) \mid L \subseteq A^n\} $$ Thus $f(n)$ is the maximal number of states of the minimal automaton of a set of words of length $n$. Then $$ f(n) = ...


2

By definition, $L^* = \bigcup_{n \geq 0} L^n$. Also, $\Sigma$ is the language of all words of length $1$ (equivalently, $\Sigma$ is the alphabet). So $\Sigma^* = \bigcup_{n \geq 0} \Sigma^n$. There is no particular reason to assume that $\Sigma^* = L^*$. For example, suppose that $\Sigma = \{a,b\}$ while $L = \{a\}$. Then $\Sigma^*$ consists of all words ...


2

The language $L_1$ is regular since it's finite. The language $L_1 \cup L_2 = \{a^n b^n : n \geq 0\}$ is classically not regular. If $L_2$ were regular then so would $L_1 \cup L_2$ be (why?), so $L_2$ cannot be regular.


2

Any language presentable by a regular expression is regular, as pointed out in a comment. This intuition can help you to see that certain languages are not regular, without a formal proof. For example, if arbitrarily long different parts of a string in the language are related somehow, e.g. your language is $a^nb^n$ for all natural numbers $n$, then it ...


1

The point is that whenever you have a word in the language, you can assume without loss of generality that the length of the $w$ component is exactly one symbol. If somebody gives you a word with a longer $w$, you can just move all of the symbols except for the first into $x$ and $y$ instead, and get a different proof that the same word is in the language. ...


1

I would work directly with the sets. Suppose that $w\in A^*B$. Then either $w\in B$, or there is are a positive integer $n$ and words $a_1,\ldots,a_n\in A$ and $b\in B$ such that $w=a_1\ldots a_nb$. In the first case $w\in B\subseteq AA^*B\cup B$, and in the second case $a_2\ldots a_n\in A^*$, so $w\in AA^*B\subseteq AA^*B\cup B$. Thus, $A^*B\subseteq ...


1

How many states are required by a deterministic finite automaton to store m words each of length n? Like J.-E. Pin seems, I too believe this means no bit words, but plain old symbol words (which only makes a difference if the alphabet has three symbols or more). So the DFA has an alphabet $\Sigma$ and we have the task to make it accept $m$ given ...


1

Though finite-state automata do not have any form of "memory" (unlike, say, pushdown automata), it is possible to use the states themselves to store a finite amount of data, in the form of $n$ bits that the automaton can access at any time. In particular, define an n-bit automaton (not standard terminology) as something like a finite-state automaton except: ...



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