2
$\begingroup$

I have the following problem. I need to determine whether this language is regular or not:

$L:= \{ w \in \Sigma^*: \forall \alpha ∈ \Sigma, |w|_\alpha \text{ is even or divisible by 3}\}$

$|w|_\alpha$ => $|w|$ is the length of the word $w$ and $|w|_\alpha$ is the number of $\alpha$ characters in that word.

For example: $w$ = 100111 => $|w|$=6, $|w|_0$ = 2, $|w|_1$ = 4.

I know that I need to use deterministic/non-deterministic finite automata, regular expression/grammar to prove that it is regular or to use pumping lemma to prove that it is not.

But I'm not sure how to approach this problem to start proving something. Is this trial and error method or is there some way to know from the start?

I appreciate your help!

$\endgroup$
  • $\begingroup$ May I ask why you edited this to remove the specification of the language? That makes it impossible to understand the question. $\endgroup$ – D.W. Apr 15 at 4:17
4
$\begingroup$

I'm not aware of any completely "algorithmic" method to decide whether a language is regular.

For the specific language you are interested in, you can start by observing that it can be written as combination of unions and intersections of a finite number of regular languages: $$ \bigcap_{\alpha \in \Sigma} \left( L_{2,\alpha} \cup L_{3,\alpha} \right), $$ where:

  • $L_{2,\alpha}$ is the language containing all words $w$ such that $|w|_\alpha$ is divisible by 2.

  • $L_{3,\alpha}$ is the language containing all words $w$ such that $|w|_\alpha$ is divisible by 3.

It is easy to show that all these languages are regular (since, in each language, $\alpha$ is now fixed). A DFA for $L_{2,\alpha}$ has two states $q_0, q_1$ where $q_i$ means that the number of characters equal to $\alpha$ encountered so far is $i$ modulo 2. A DFS for $L_{3,\alpha}$ is similar but has $3$ states.

The regularity of $L$ follows from the fact that regular languages are closed under union and intersection.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

This type of question often rises when starting to learn the theoretic aspect of computer science.

The answer, which may seem unfortunate at first, is that there is no algorithmic way of determining whether a language is regular. Moreover, there will never be an algorithmic way, no matter what advances in computers the future may bring, and how many clever people try to come up with algorithms.

Now, this is a pretty strong claim, so I should back this up. Technically, the reason for this is that the problem of determining, given a Turing Machine, whether its language is regular, is undecidable. Presumably, since you're just getting into automata theory, you're not familiar with undecidability yet. But when you will be, this will all make sense. Also, it will all be very very exciting, as these results are simply mind blowing (in my opinion).

As an additional note, the question "is a given language regular?" should be carefully formulated. Specifically, how is the language given?

  • If it's given by an automaton -- then it's regular (but that's just silly).
  • If it's given by a regular expression -- then it's regular (but that requires some work to prove).
  • If it's given by a Turing Machine -- it's undecidable whether it's regular.
  • If it's given by a different model, the it depends. For example, for CFG's, the problem is still undecidable. But for simpler models it may be decidable.

I guess all of this is not what you were aiming at with your question, since you were probably given a certain language described in English, and you're just trying to get intuition on whether it's regular. The good news on this front, is that by the time you solve 10 such questions, you'll probably have enough intuition for all the exercises you'll be given.

A good rule of thumb is that regular languages cannot "count" arbitrarily. They can count up to a fixed number (e.g., couting modulo 6, counting up to 13, etc.) but they cannot e.g., compare the number of a's to the number of b's.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

How would you prove that L is regular? You can prove it by giving a regular expression or a finite state machine. And we know that finite languages are regular, and if L1 and L2 are regular then the complement of L1, and the union or intersection of L1 and L2 are regular, and with that finite set operations between regular languages are regular.

How would you prove that L is not regular? A common approach is this: Assume that you have a finite state machine for L. If Ax is in L and Bx is not, then parsing either A or B from the initial state must end in different states. If we can use this to prove that the set of statea is not finite, then L is not regular.

Why would these approaches fail? The language L must be specified in some way. If it is given by a context free grammar (CFG) for example, and we find a regular expression for it, then we have the problem that it is undecidable whether a CFG and a regular expression specify the same language!

On the other hand, given the description of a language we might find it hard or impossible to decide if a string belongs to a language at all. Take {$a^n: $There are infinitely many primes p such that p+n is also prime}. We don’t know if aa belongs to the language (that's the twin prime conjecture), but we know aaa doesn’t. That’s just two hard things you’d be up against if you wanted to find a general method to decide regularity.

| cite | improve this answer | |
$\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.