# No FSM/Regex exists for this language right?

The language is this:

$$L = \{w \in \{a,b\}*:$$ each $$a$$ has a matching $$b$$ somewhere in $$w$$ $$\}$$

This wouldn't have an FSM since you'd need infinite states of depth for each unmatched a you have, right?

• What do you mean by "matching"? Do you mean the number of $a$ is no more than the number of $b$? – xskxzr Sep 27 '19 at 4:01
• – Evil Sep 27 '19 at 13:19
• Or do you mean: a bijective mapping can be constructed between the $a$s and the $b$s? (In other words, the number of $a$s and $b$s is equal.) – reinierpost Oct 3 '19 at 17:53

## 2 Answers

Expanding on Daniel Martin's answer. None of the following interpretations yields a regular language:

• $$L = \{ w \in \{a,b\}^* : \exists n \ge 0, \; w = a^n b^n \}$$
• $$L$$ contains all the words $$w \in \{a,b\}^*$$ such that the number of $$a$$s in $$w$$ is not larger than the number of $$b$$s in $$w$$.
• $$L$$ contains all the words $$w \in \{a,b\}^*$$ such that the number of $$a$$s in $$w$$ is equal than the number of $$b$$s in $$w$$.
• $$L$$ contains all the words $$w \in \{a,b\}^*$$ such that there is a injective/bijective mapping that maps each a $$a$$ that appears in a generic position $$i$$ in $$w$$ with a $$b$$ in $$w$$ that appears in a position $$j>i$$.

The proof is the same for all cases: if $$L$$ was regular then, for a sufficiently large $$n$$, the word $$w = a^n b^n \in L$$ could be written as $$w = a^{n-k} a^k b^n$$ (with $$1 \le k \le n)$$ in such a way that $$a^{n-k}a^{k \cdot h} b^n \in L$$ for all choices of $$h \in \mathbb{N}$$ (see pumping lemma for regular languages). This is a contradiction since $$a^{n-k}a^{2k} b^n = a^{n+k}b^{n} \not\in L$$.

As the comments say, it isn't completely clear what you mean by "matching", but if you mean that for any positive integer $$n$$, the string $$\mathtt{a}^n\mathtt{b}^n$$ (that is, the string of $$n$$ "$$\mathtt{a}$$"s followed by $$n$$ "$$\mathtt{b}$$"s) is in the language, but $$\mathtt{a}^n\mathtt{b}^{n-1}$$ is not in the language, then what you say is correct: $$L$$ is not a regular language because you would need an infinite number of states, at least one for every string of the form $$\mathtt{a}^n$$.