Welcome to our community

Be a part of something great, join today!

Language of Automata

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,133
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
Mar 5, 2012
8,878
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!

What is your start state?

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
Apr 14, 2013
4,133
Hi mathmari!

What is your start state?

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
Mar 5, 2012
8,878

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,133
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
Mar 5, 2012
8,878
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
Apr 14, 2013
4,133
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
Mar 5, 2012
8,878
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
Apr 14, 2013
4,133
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
Apr 14, 2013
4,133
How can the state Q2 go with b to the state Q1 and also to the state Q3? :confused:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,878
How can the state Q2 go with b to the state Q1 and also to the state Q3? :confused:
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. ;)