0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.