Can an automaton be produced for a language that outputs undefined for the empty string?

Question

Say I have the below language and I would like to produce an automaton for it:

$$ { \{ s \mid \text{length}(s) \div \text{length(filter}(s)) = 2\}} $$

• length returns the length of the string
• filter returns its input string without any letter a's

It is to be noted that upon inputting the empty string in such a language, the output is undefined.

Can an automaton be produced despite having the empty string as input return an undefined output?

Answer 1

Since the alphabet is $\{a,b\}$, one has $|u| = |u|_a + |u|_b$, where, as usual, $|u|_a$ denotes the number of occurrences of $a$ in $u$ and $|u|$ is the length of $u$. Now, $|u| = 2|u|_b$ if and only if $|u|_a + |u|_b = 2|u|_b$, that is, $|u|_a = |u|_b$.

Suppose that the language $L = \{ u \in \{a,b\}^* \mid |u|_a = |u|_b \}$ is regular. Then the language $L \cap a^*b^*$ would also be regular. But $L \cap a^*b^* = \{a^nb^n \mid n \geqslant 0\}$, the standard example of a context-free, but non-regular language. The proof can be found in any textbook on automata, and can be proved using Nerode's equivalence or by the pumping lemma.

Answer 2

The language $L:={ \{ s \mid \text{length}(s) \div \text{length(filter}(s)) = 2\}}$ is not regular.

You can see it using the pumping lemma :

Assume (for contradiction) that $L$ is regular. Then there is some integer $l$ such that whenever a word $w\in L$ has length greater than $l$, there are words $u_1,v,u_2$ satisfying :

• $v\neq \epsilon$
• $length(u_1v)\leqslant l$
• $\forall n \in \mathbb{N}, \, u_1v^nu_2\in L$

Now consider the word $$w:=\underbrace{aa\dots a}_{l \textrm{ times}}\underbrace{bb\dots b}_{l \textrm{ times}}$$

$w\in L$ and $length(w)\geqslant l$, hence we can find $u_1,v,u_2$ as above, hence $w':=u_1v^2u_2\in L$, but $w'$ has strictly more than $l$ "$a$"s, while it has $l$ "b"s (and no other letters), hence $w' \notin L$, a contradiction.