Exploring Language Recognition and DFA Creation

[evinda]

Hello! (Wave)

The following DFA is given:

View attachment 5685

I want to find the language that it recognizes. The alphabet is $\Sigma=\{0,1\}$.

Isn't the language this one: $(0^{\ast} 1^{+} 0^{\ast} )^{+}$?

Also I want to draw a dfa that recognizes the following languages and that have the referred number of states. The alphabet is still $\{0,1\}$.

• $\{0\}$, with two states
• $1^{\ast} (001^+)^{\ast}$, with 3 states
• $\{ \epsilon \}$ , with 1 state
• $0^{\ast}$ with 1 state

• View attachment 5686

But can it be that $1$ goes nowhere?

• View attachment 5687

But then the word $1$ isn't accepted... :( What could we change?

• View attachment 5688

Can it be that 0 and 1 go nowhere? (Worried)

• View attachment 5689

Again $1$ goes nowhere... Is that possible?

 

[I like Serena]

Hey evinda! (Wave)

Isn't the language this one: $(0^{\ast} 1^{+} 0^{\ast} )^{+}$?

Does the DFA allow a $0$ at the end? (Wondering)

Also I want to draw a dfa that recognizes the following languages and that have the referred number of states. The alphabet is still $\{0,1\}$.

• $\{0\}$, with two states

But can it be that $1$ goes nowhere?

It depends on the definition of a DFA that you have. Does it allow that? (Wondering)
As far as I'm concerned, it should be fine if $1$ doesn't go anywhere - it keeps the DFA simple and straight forward.
But if we want $1$ to go somewhere as well, we can introduce a new state that we call sink and define a transition for $1$ to it. Since it's not a final state, the machine can be "stuck" there and not accept the word.

Btw, shouldn't there be an arrow identifying the start state?

• $1^{\ast} (001^+)^{\ast}$, with 3 states

But then the word $1$ isn't accepted... What could we change?

You didn't identify the start state yet.
How about making $q_3$ the start state?

Btw, doesn't your machine accept an arbitrary number of consecutive $0$'s? Should it? (Wondering)

• $\{ \epsilon \}$ , with 1 state

Can it be that 0 and 1 go nowhere?

• $0^{\ast}$ with 1 state

Again $1$ goes nowhere... Is that possible?

Same thing, if necessary we can introduce a sink state.

 

[evinda]

Does the DFA allow a $0$ at the end? (Wondering)

No, it doesn't... (Shake) So should the language be of the following form?

$(0^{\ast} 1^+ 0^{+}1)^{\ast}$

It depends on the definition of a DFA that you have. Does it allow that? (Wondering)

View attachment 5690

View attachment 5691

As far as I'm concerned, it should be fine if $1$ doesn't go anywhere - it keeps the DFA simple and straight forward.
But if we want $1$ to go somewhere as well, we can introduce a new state that we call sink and define a transition for $1$ to it. Since it's not a final state, the machine can be "stuck" there and not accept the word.

Btw, shouldn't there be an arrow identifying the start state?

So you mean that the DFA could be drawn as follows?

View attachment 5692

Btw, doesn't your machine accept an arbitrary number of consecutive $0$'s? Should it? (Wondering)

It does... But, it shouldn't... (Worried)

You didn't identify the start state yet.
How about making $q_3$ the start state?

View attachment 5693

But now we have again consecutive 0s ... What could we do to change that? (Thinking)

 

[I like Serena]

No, it doesn't... (Shake) So should the language be of the following form?

$(0^{\ast} 1^+ 0^{+}1)^{\ast}$
https://www.physicsforums.com/attachments/5685

How about the word $1$? Does the DFA accept it? And your expression? (Wondering)Let's go through this state by state.
In state q1 we can accept $0^*$ followed by $1$ to q2 followed by $1\ast$ after which we can stop.
That is: $0^* 1 1^* = 0^* 1^+$.

After that, we can go back to q1 with $0$, followed by $0^*$, followed again by $1 1^*$ after which we can stop.
So: $0^* 1 1^* 0 0^* 1 1^* = 0^* 1^+ 0^+ 1^+$.

And we can keep going to get: $0^* 1^+ 0^+ 1^+ 0^+ 1^+ 0^+ 1^+ ...$.

So we can have:
$$
0^* 1^+ \\
0^* 1^+ 0^+ 1^+ \\
0^* 1^+ 0^+ 1^+ 0^+ 1^+ 0^+ 1^+ ...
$$
Hmm, how can we abbreviate that? (Wondering)

https://www.physicsforums.com/attachments/5690
View attachment 5691

The fact that $\delta$ is a function of $Q\times \Sigma$ implies that every state should have outgoing arrows for each input symbol.
However, with the number of supposed states that is given for each problem, there is no room for a sink. (Nerd)

Btw, it specifies that the start state should be $q_0$, but that's not the case in your DFA's.

So you mean that the DFA could be drawn as follows?

I was thinking more of:
View attachment 5694
However, the problem statement says you should have 2 states, so I don't think you're supposed to include a sink.

It does... But, it shouldn't... (Worried)

But now we have again consecutive 0s ... What could we do to change that? (Thinking)

Let's start with introducing new states where needed.
We should get the following DFA:
View attachment 5696
Agreed? (Wondering)

However, we should have 3 states instead of 4.
Fortunately states $q_0$ and $q_3$ look the same.
Could we leave out $q_3$ and redirect its arrows to $q_0$? (Wondering)

 

[Evgeny.Makarov]

1. It would be better to devote its own thread to every question. Discussing five automata in one thread is confusing.

2. I believe you are using the Sipser's book "Introduction To The Theory Of Computation". There the transition function of a DFA returns a state and is total, i.e., every state must have an outgoing arrow for every symbol. This is in contrast to NFAs, where the transition function returns a set (possibly empty) of states. I believe it is not possible to construct a DFA with one state accepting $\{\varepsilon\}$ or $0^*$,but it is possible to construct such NFAs.

3. It would be helpful of you specify exercise numbers if exercises are taken from the Sipser's book.

 

[evinda]

How about the word $1$? Does the DFA accept it? And your expression? (Wondering)Let's go through this state by state.
In state q1 we can accept $0^*$ followed by $1$ to q2 followed by $1\ast$ after which we can stop.
That is: $0^* 1 1^* = 0^* 1^+$.

After that, we can go back to q1 with $0$, followed by $0^*$, followed again by $1 1^*$ after which we can stop.
So: $0^* 1 1^* 0 0^* 1 1^* = 0^* 1^+ 0^+ 1^+$.

And we can keep going to get: $0^* 1^+ 0^+ 1^+ 0^+ 1^+ 0^+ 1^+ ...$.

So we can have:
$$
0^* 1^+ \\
0^* 1^+ 0^+ 1^+ \\
0^* 1^+ 0^+ 1^+ 0^+ 1^+ 0^+ 1^+ ...
$$
Hmm, how can we abbreviate that? (Wondering)

So the language is this one: $0^{\ast} 1^+ (0^+ 1^+)^{\ast}$, right?

The fact that $\delta$ is a function of $Q\times \Sigma$ implies that every state should have outgoing arrows for each input symbol.
However, with the number of supposed states that is given for each problem, there is no room for a sink. (Nerd)

(Nod)

Let's start with introducing new states where needed.
We should get the following DFA:

Agreed? (Wondering)

However, we should have 3 states instead of 4.
Fortunately states $q_0$ and $q_3$ look the same.
Could we leave out $q_3$ and redirect its arrows to $q_0$? (Wondering)

Yes... (Nod) Ah, I see... Then the DFA will be the following, right?

View attachment 5697

Does this often happen that we draw a dfa with one more state than the desired number and that the final state is equal to the initial one?

- - - Updated - - -

1. It would be better to devote its own thread to every question. Discussing five automata in one thread is confusing.

2. I believe you are using the Sipser's book "Introduction To The Theory Of Computation". There the transition function of a DFA returns a state and is total, i.e., every state must have an outgoing arrow for every symbol. This is in contrast to NFAs, where the transition function returns a set (possibly empty) of states. I believe it is not possible to construct a DFA with one state accepting $\{\varepsilon\}$ or $0^*$,but it is possible to construct such NFAs.

3. It would be helpful of you specify exercise numbers if exercises are taken from the Sipser's book.

I found these exercises from some notes of computability theory, but the most of them are from the Sipser's book. Next time I will specify the exercise numbers.

So these exercises are examples of situations where NFAs are needed, right?

 

[Evgeny.Makarov]

So these exercises are examples of situations where NFAs are needed, right?

Why don't you look at the exact statement of the problem? But the only DFAs with one state in the language $\{0,1\}$ are the ones accepting $\emptyset$ and $\{0,1\}^*$.

 

[evinda]

Why don't you look at the exact statement of the problem?

At the book that I have I found the statement I have written above.

According to the online version I have, the statement is the following:

View attachment 5698

So the latter should be the right problem statement.

So are the above automata the right NFAs?

- - - Updated - - -

But the only DFAs with one state in the language $\{0,1\}$ are the ones accepting $\emptyset$ and $\{0,1\}^*$.

Do we have the DFA that accepts only the $\emptyset$ if $q_0$ is a non-accepting state and the DFA that accepts $\{0,1\}^*$ otherwise?

 

[I like Serena]

2. I believe you are using the Sipser's book "Introduction To The Theory Of Computation". There the transition function of a DFA returns a state and is total, i.e., every state must have an outgoing arrow for every symbol. This is in contrast to NFAs, where the transition function returns a set (possibly empty) of states. I believe it is not possible to construct a DFA with one state accepting $\{\varepsilon\}$ or $0^*$,but it is possible to construct such NFAs.

I've always been a bit confused about these definitions.
The FA's we have here are all deterministic, even though not all input symbols have a state transition.
Still, we can consider every missing symbol to have an implicit transition to an extra sink state.
That's very different from a non-deterministic FA that would typically have multiple state transitions for the same symbol.
So what's the big deal that a DFA is supposed to have a transition for every symbol?

So the language is this one: $0^{\ast} 1^+ (0^+ 1^+)^{\ast}$, right?

Yes. We can even further abbreviate it to $(0^*1^+)^+$. (Nod)

Yes... (Nod) Ah, I see... Then the DFA will be the following, right?

Does this often happen that we draw a dfa with one more state than the desired number and that the final state is equal to the initial one?

Yes. We will have to do whatever is required for the problem statement.
Usually there is no real need to reduce the number of states though - it's just an optimization that happens to look more pleasing to the eye and is less work to draw. (Wink)

 

[Evgeny.Makarov]

So are the above automata the right NFAs?

Sorry, as I said, this thread contains many automata for various problems, both correct and incorrect. I am reluctant to go over the whole thread and give my opinion for each of them. Either summarize the latest information or start a new thread for each problem.

Do we have the DFA that accepts only the $\emptyset$ if $q_0$ is a non-accepting state and the DFA that accepts $\{0,1\}^*$ otherwise?

Yes.

I've always been a bit confused about these definitions.
The FA's we have here are all deterministic, even though not all input symbols have a state transition.
Still, we can consider every missing symbol to have an implicit transition to an extra sink state.
That's very different from a non-deterministic FA that would typically have multiple state transitions for the same symbol.
So what's the big deal that a DFA is supposed to have a transition for every symbol?

I agree, whether the transition function is total or not does not change the concept of the automaton significantly: it's still essentially a DFA. In contrast, if the function returns sets of states instead of individual states, this is a very different concept: an NFA. I am just saying that any questions and confusion is unnecessary if we stay within the realm of the book. Instead of defining the transition function of DFA as $\delta:Q\to Q\cup\{\emptyset\}$ and considering special cases in definitions and proofs, the author chose to consider the output $\emptyset$ only in NFAs, which makes the treatment uniform. Each problem clearly states whether it requires a DFA or an NFA. Then why complicate the situation and wonder if problem statements should be changed?

 

[evinda]

Thanks for your answers! (Smirk)