1
$\begingroup$

I was wondering if one could prove that a language is regular without showing a DFA/NFA or a regular expression that expresses it.

For example: $L = \{w \in \Sigma^* : w \text{ has at least two identical letters} \}$

$\endgroup$
  • $\begingroup$ Yes you can - You could use the pumping lemma. See:en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages $\endgroup$ – Nizbel99 Oct 29 '13 at 13:37
  • 2
    $\begingroup$ No the pumping lemma is used when you want to show that a language is NOT regular. It cannot be used the other way, since there are nonregular languages satisfying the pumping lemma. $\endgroup$ – Denis Oct 29 '13 at 13:41
1
$\begingroup$

In this case it’s not hard to design a DFA that accepts the $L$.

For each $S\subseteq\Sigma$ give your DFA a state $q(S)$, and have one other state $q$ as well. Make $q(\varnothing)$ the initial state, and make $q$ the only acceptor state. For each $s\in\Sigma$ and $S\subseteq\Sigma$, the $s$-transition from $q(S)$ goes to $q(S\cup\{s\})$ if $s\notin S$ and to $q$ otherwise. All transition from $q$ are to $q$. It’s not hard to see that if you’re in state $q(S)$, you’ve seen each character in $S$ once; the moment you see a character a second time, you go to state $q$, and the word is accepted.

In general, however, the answer to your question is yes: there are ways to show that a language is regular without constructing a DFA, NFA, regular expression, or regular grammar for it, though only after one has proved some results that do use these methods. For example, if we know that $L_1$ and $L_2$ are regular, we can conclude that $L_1\cap L_2$ is regular, because the class of regular languages is closed under intersection. However, the proof of this fact uses one of the explicit characterizations.

$\endgroup$
0
$\begingroup$

Yes you have several other techniques to show that a language is regular.

For instance you can show that the Myhill-Nerode equivalence has finite index, or you can exhibit a finite monoid recognizing your language.

You can also use a MSO sentence to describe your language, which may be the simplest way: for instance your language $L$ is recognized by the sentence $\exists x,\exists y\neq x, \bigvee_{a\in \Sigma} a(x)\wedge a(y)$, which is a proof that $L$ is regular.

This last method is convenient, since the MSO sentence is often quite close to the "intuitive" definition of your language: the above sentence just requires that there are two positions in the word labelled by the same letter, which is exactly how you defined your language in the first place.

$\endgroup$
0
$\begingroup$

There is an interesting example which relies on the notion of subword. A word $u$ is a subword of $v$ if $u$ can be obtained from $v$ by deleting some letters (not necessarily consecutive ones). For instance, $nesting$ is a subword of $i\color{red}{n}ter\color{red}{esting}$.

Now, take any language $L$ on the alphabet $A$ (regular or not) and let $R(L)$ be the language of all words of $A^*$ having at least one subword in $L$. Then one can show that $R(L)$ is always regular (this is a consequence of the fact that the subword order is a well quasi order), but there is no way to find a DFA for $R(L)$ if $L$ is, say, a non recursively enumerable language.

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