MHB Answer: Language of Automata: DFA Q1, Q2

[mathmari]

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

 

[I like Serena]

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]

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.

 

[I like Serena]

The start state is Q1.
I want the language as a regular expression.

Then I guess I've already answered your question...

 

[mathmari]

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*$ ?

 

[I like Serena]

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]

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.

 

[I like Serena]

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]

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]

How can the state Q2 go with b to the state Q1 and also to the state Q3?

 

[I like Serena]

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. ;)