Language of Automata

mathmari

Well-known member
MHB Site Helper
Hi! Could you help me finding the language that is accepted by the DFA with the following state diagram?

___| a ____ b
Q1 | Q2 __ Q1
Q2 | Q2 __ Q3
Q3 | Q3 __ Q3

final states: Q1, Q2

Klaas van Aarsen

MHB Seeker
Staff member
Hi! Could you help me finding the language that is accepted by the DFA with the following state diagram?

___| a ____ b
Q1 | Q2 __ Q1
Q2 | Q2 __ Q3
Q3 | Q3 __ Q3

final states: Q1, Q2
Hi mathmari!

If Q3 is not a final state, you can never go to Q3, since you can never go back.
Is that what you intended?

How do you want your language?
As a regular expression?
In BNF syntax? Or EBNF?

If you start in state Q1, the words you can form are $b*a*$, where $*$ denotes zero or more.
Starting from state Q2, you can only form $a*$, which is already included.

mathmari

Well-known member
MHB Site Helper
Hi mathmari!

If Q3 is not a final state, you can never go to Q3, since you can never go back.
Is that what you intended?

How do you want your language?
As a regular expression?
In BNF syntax? Or EBNF?

If you start in state Q1, the words you can form are $b*a*$, where $*$ denotes zero or more.
Starting from state Q2, you can only form $a*$, which is already included.
The start state is Q1.
I want the language as a regular expression.

Klaas van Aarsen

MHB Seeker
Staff member
The start state is Q1.
I want the language as a regular expression.

mathmari

Well-known member
MHB Site Helper
If you start in state Q1, the words you can form are $b*a*$, where $*$ denotes zero or more.
Starting in state Q1, couldn't the words be also $a*b*$ ?

Klaas van Aarsen

MHB Seeker
Staff member
Starting in state Q1, couldn't the words be also $a*b*$ ?
After you accept the first $a$, accepting a $b$ would bring you to state Q3.
And from state Q3 you can never get to a final state anymore.

It is a bit weird though that you would have a state that doesn't go anywhere.
Are you sure that is right?

mathmari

Well-known member
MHB Site Helper
After you accept the first $a$, accepting a $b$ would bring you to state Q3.
And from state Q3 you can never get to a final state anymore.

It is a bit weird though that you would have a state that doesn't go anywhere.
Are you sure that is right?
Now I looked at the exercise again and realized that the state Q2 with $b$ goes to the state Q1 and to the state Q3.

Klaas van Aarsen

MHB Seeker
Staff member
Now I looked at the exercise again and realized that the state Q2 with $b$ goes to the state Q1 and to the state Q3.
So your transition table is incomplete?
But still no other transitions starting from state Q3?

mathmari

Well-known member
MHB Site Helper
So your transition table is incomplete?
But still no other transitions starting from state Q3?
Starting from Q3 with $a$ or $b$ it goes to the state Q3 again...

mathmari

Well-known member
MHB Site Helper
How can the state Q2 go with b to the state Q1 and also to the state Q3?

Klaas van Aarsen

MHB Seeker
Staff member
How can the state Q2 go with b to the state Q1 and also to the state Q3?
Now that you mention it, that's not really deterministic is it?
However, if it would go to state Q3, it can never reach a final state anymore.

In my opinion, your state machine is screwed up.
State Q3 should be deleted altogether, including all transitions toward it.
Then we're left with a nice and deterministic state machine.