- Thread starter
- #1

- Apr 14, 2013

- 4,133

___| a ____ b

Q1 | Q2 __ Q1

Q2 | Q2 __ Q3

Q3 | Q3 __ Q3

final states: Q1, Q2

- Thread starter mathmari
- Start date

- Thread starter
- #1

- Apr 14, 2013

- 4,133

___| a ____ b

Q1 | Q2 __ Q1

Q2 | Q2 __ Q3

Q3 | Q3 __ Q3

final states: Q1, Q2

- Admin
- #2

- Mar 5, 2012

- 8,878

Hi mathmari!

___| a ____ b

Q1 | Q2 __ Q1

Q2 | Q2 __ Q3

Q3 | Q3 __ Q3

final states: Q1, Q2

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.

- Thread starter
- #3

- Apr 14, 2013

- 4,133

The start state is Q1.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.

I want the language as a regular expression.

- Admin
- #4

- Mar 5, 2012

- 8,878

Then I guess I've already answered your question...The start state is Q1.

I want the language as a regular expression.

- Thread starter
- #5

- Apr 14, 2013

- 4,133

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

- Admin
- #6

- Mar 5, 2012

- 8,878

After you accept the first $a$, accepting a $b$ would bring you to state Q3.Starting in state Q1, couldn't the words be also $ a*b*$ ?

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?

- Thread starter
- #7

- Apr 14, 2013

- 4,133

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.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?

- Admin
- #8

- Mar 5, 2012

- 8,878

So your transition table is incomplete?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.

But still no other transitions starting from state Q3?

- Thread starter
- #9

- Apr 14, 2013

- 4,133

Starting from Q3 with $a$ or $b$ it goes to the state Q3 again...So your transition table is incomplete?

But still no other transitions starting from state Q3?

- Thread starter
- #10

- Apr 14, 2013

- 4,133

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

- Admin
- #11

- Mar 5, 2012

- 8,878

Now that you mention it, that's not really deterministic is it?How can the state Q2 go with b to the state Q1 and also to the state Q3?

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.