What is the language of this deterministic finite automata?

Question

Given:

I have no idea what the accepted language is.

From looking at it you can get several end results:

1.) bb
2.) ab(a,b)
3.) bbab(a, b)
4.) bbaaa

Wexford

Possible duplicate from math.stackexchange math.stackexchange.com/questions/1739863/… – Stryker

Answer 1

How to write regular expression for a DFA

In any automata, the purpose of state is like memory element. A state stores some information in automate like ON-OFF fan switch.
A Deterministic-Finite-Automata(DFA) called finite automata because finite amount of memory present in the form of states. For any Regular Language(RL) a DFA is always possible.

Let's see what information stored in the DFA (refer my colorful figure).
(note: In my explanation any number means zero or more times and Λ is null symbol)

---

State-1: is START state and information stored in it is even number of a has been come. And ZERO b.
Regular Expression(RE) for this state is = (aa)*.

State-4: Odd number of a has been come. And ZERO b.
Regular Expression for this state is = (aa)*a.

Figure: a BLUE states = EVEN number of a, and RED states = ODD number of a has been come.

NOTICE: Once first b has been come, move can't back to state-1 and state-4.

State-5: comes after Yellow b. Yellow b means b after odd numbers of a.
Once you gets b after odd numbers of a(at state-5) every thing is acceptable because there is self a loop for (b,a) at state-5.

You can write for state-5 : Yellow-b followed-by any string of a, b that is = Yellow-b (a + b)*

State-6: Just to differentiate whether odd a or even.

State-2: comes after even a then b then any number of b. = (aa)* bb*

State-3: comes after state-2 then first a then there is a loop via state-6. We can write for state-3 comes = state-2 a (aa)* = (aa)*bb* a (aa)*

Because in our DFA, we have three final states so language accepted by DFA is union (+ in RE) of three RL (or three RE).
So the language accepted by the DFA is corresponding to three accepting states-2,3,5, And we can write like:

 State-2 +  state-3           + state-5    

(aa)*bb* + (aa)*bb* a (aa)* + Yellow-b (a + b)*

I forgot to explain how Yellow-b comes?
ANSWER: Yellow-b is a b after state-4 or state-3. And we can write like:

Yellow-b = ( state-4 + state-3 ) b = ( (aa)*a + (aa)*bb* a (aa)* ) b

[ANSWER]
(aa)*bb* + (aa)*bb* a (aa)* + ( (aa)*a + (aa)*bb* a (aa)* ) b (a + b)*

---

English Description of Language: DFA accepts union of three languages

• EVEN NUMBERs OF a's, FOLLOWED BY ONE OR MORE b's,
• EVEN NUMBERs OF a's, FOLLOWED BY ONE OR MORE b's, FOLLOWED BY ODD NUMBERs OF a's.
• A PREFIX STRING OF a AND b WITH ODD NUMBER OF a's, FOLLOWED BY b, FOLLOWED BY ANY STRING OF a AND b AND Λ.

English Description is complex but this the only way to describe the language. You can improve it by first convert given DFA into minimized DFA then write RE and description.

---

Also, there is a Derivative Method to find RE from a given Transition Graph using Arden's Theorem. I have explained here how to write a regular expression for a DFA using Arden's theorem. The transition graph must first be converted into a standard form without the null-move and single start state. But I prefer to learn Theory of computation by analysis instead of using the Mathematical derivation approach.

Bogoch

Answer 2

I guess this question isn't relevant anymore :) and it's probably better to guide you through it then just stating the answer, but I think I got a basic expression that covers it (it's probably minimizable), so i'll just write it down for future searchers

(aa)*b(b)* // for stoping at 2
U
(aa)*b(b)*a(aa)* // for stoping at 3
U
(aa)*b(b)*a(aa)*b((a)*(b)*)* // for stoping at 5 via 3
U
a(aa)*b((a)*(b)*)* // for stoping at 5 via 4

Post

Answer 3

The examples (1 - 4) that you give there are not the language accepted by the DFA. They are merely strings that belong to the language that the DFA accepts. Therefore, they all fall in the same language.

If you want to figure out the regular expression that defines that DFA, you will need to do something called k-path induction, and you can read up on it here.

Deputize

ok, I'm not completely sure but I came up with : it must contain a {b} and have an odd number of {a}. – Wexford

Kleene's theorem gives algorithms for producing an NFA-Lambda or a RE given a RE or a FA, respectively. – Wheatley

This answer should have more upvotes IMO. The link you provide gives a great explanation (by Jeff Ullmann!). – Tardy