0
$\begingroup$

I'm trying to figure out which language can be recognized in this automaton

Automata http://cdn.imghack.se/images/64b81d259a1d403b810dd9744dc222f7.jpg

According to Wikipedia here "The language L ⊆ Σ* recognized by an automaton is the set of all the words that are accepted by the automaton."

So using what Wikipedia states and knowing that this automaton is a finite state automaton, I would dare to say that this automaton accepts regular languages.

If I would use M to define this automaton then I could say:

The language recognized by M is the regular language given by a certain regular expression.

But I'm having a a hard time figuring out the regular expression.

I'm not sure of about this but here is what I think the regular expression looks like

$$ L = (a|b)(a|b)^*a^* $$

I would appreciate any help in this matter

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Some terminology stuff: it accepts a regular language. A particular automaton accepts ONE language, which may contain many words. The class of finite state automata accept the family of regular languages. But a particular DFA accepts a particular regular language. $\endgroup$
    – Joey Eremondi
    Commented May 14, 2014 at 15:51
  • $\begingroup$ It's always a good idea to check your regular expression by seeing if (a) it denotes a string that isn't accepted by your FA and (b) it denotes all strings that are accepted by the FA. In this case, the string $b$ is in the language denoted by your regexp, but it's not accepted by the FA. $\endgroup$
    – Rick Decker
    Commented May 14, 2014 at 17:51
  • 3
    $\begingroup$ I'm voting to close this question as unclear because the server that holds the image hasn't been responding to requests all day, so we have no way of knowing what automaton is being asked about. $\endgroup$
    – David Richerby
    Commented Oct 24, 2019 at 18:42

2 Answers 2

Reset to default
3
$\begingroup$

In general, there is a dynamic programming algorithm for converting finite automata into regular expressions. But this one is simple enough that we can eyball it.

From the start state, we have two choices. So we can see our expression has the form | where _ represents the parts of the expression yet to be filled in.

Let's look at the top branch. There we must read two a's, then as many a's or b's as we want. So this part will have the form aa(a|b)*

For the second half, we see we must read at least one a or b. Then we can loop on a or b as many times a we want, and then we must read two a's. So we get (a|b)(a|b)*aa

Notice the patterns here. When we have more than one transition coming out of a state, that represents the "|" operation. A transiton on "a,b" is equivalent to having one transition on a and another on b.

So, our final expression is (aa(a|b)*) | ((a|b)(a|b)*aa).

Any time we have a cycle, either on a particular state, or on a path of states, we get something corresponding to *. And every time we have to read something in sequence, we have concatenation.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Whoops, fixed! Sorry. $\endgroup$
    – Joey Eremondi
    Commented May 14, 2014 at 17:17
  • $\begingroup$ Which can be simplified. Note the language is "the set of $a,b$-strings that have $aa$ either as prefix or as suffix". The bottom half with $aa$ suffix seems to require that the strings are at least three letters long, but nothing changes when we drop this condition as the two letter string $aa$ is already accepted by the top branch: aa(a+b)* + (a+b)*aa. $\endgroup$
    – Hendrik Jan
    Commented May 31, 2014 at 23:20
-2
$\begingroup$

Minimise the Automaton, as it is a Finite Automaton, so we can apply the method of minimising states. The RegEx will be formed that describes the language recognised by this automaton.

Edit: this answer seems to be wrong, please refer to David's comment below.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Minimizing the automaton doesn't produce a regular expression: it just produces a smaller automaton. And somebody who can't work out what langauge is accepted by what is probably quite a small automaton (I can't access the image at the moment) probably isn't going t obe able to do more difficult things, such as minimizing. $\endgroup$
    – David Richerby
    Commented Oct 24, 2019 at 9:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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