understanding DFA

[zak100]

Hi,

The above DFA has 3 final states: q0, q1 and q3  and q0 as its start state. It accepts strings: b, ba, bab, baba. Somebody please guide me whether it accepts aa or bb as a substring?I think it accepts string: abbaa. I want to create a DFA which does not accept aa and bb as substrings.

 

Zulfi.

 

 

 

Similalry the following one:

 

 

 

 

 

I think this one does not accept aa and bb but its not correct because it does not accept any string.

 

Somebody please guide me.

 

Zulfi.

Edited September 21, 2020 by zak100

[fiveworlds]

Quote

I think this one does not accept aa and bb but its not correct because it does not accept any string.

You are correct. You could modify it to have a final state somewhere that transitions on some other letter like c?

A DFA must end on a final state e.g. the 2 circles.

Starting from q3 you can accept aa as it will transition to q0 then q1.

Starting from q1 you can accept bb as it will transition to q0 them q3.

Quote

 I want to create a DFA which does not accept aa and bb as substrings.

You can read more than one letter at a time and make all final states lead to an exit state if it reads them. You can use anything that fits in combinatorial logic including don't care terms to read a regex e.g. BxBxxxB.

***** Challenge Question *****

A DFA is a part of a Turing machine. Show that a 3 head Turing Machine can accept the regex B*B*B without changing state by creating a table of moves. Hint. You may stop moving a read head if you read a letter. 

Edited September 21, 2020 by fiveworlds

[zak100]

Hi,

Thanks a lot for your explanation.

Quote

A DFA must end on a final state e.g. the 2 circles.

Starting from q3 you can accept aa as it will transition to q0 then q1.

Starting from q1 you can accept bb as it will transition to q0 them q3.

If we include 'c', should not we provide 'c' input for all states?

Zulfi.

 

[zak100]

Hi,

What is the difference between (3) and (4)?

 

The above (3) does not seem to accept substring "bb" but does the above accept  "aa"?

 

What is the difference between (3) and (4)? Does the (4) accept "aa"?

Somebody please guide me.

 

Zulfi.

 

 

 

[Ghideon]

2 hours ago, zak100 said:

What is the difference between (3) and (4)? Does the (4) accept "aa"?

 

In (4) there are two paths labeled "a" from the same state (see the purple arrow), is that valid? How would one select which one to follow?

 

 

[zak100]

Hi,

Yes you are right. Okay then please tell me about (3) alone. Can the start  state  produce string of repeated 'a's to  be accepted in the final state?

 

Zulfi.

[Ghideon]

11 minutes ago, zak100 said:

Okay then please tell me about (3) alone. Can the start  state  produce string of repeated 'a's to  be accepted in the final state?

Lets name the states: purple letters X, Y, Z, Q. I assume Y is the accept state and X is the start state. I assume "repeated 'a's to be accepted in the final state" means that you mean if any sequence of "aa", "aaa", "aaaa" etc takes us from the starting state X to the accept state Y. 

-I assume we start from X
-We get an "a" taking us to state Y. 
-We get another "a" and that takes us to Z. Since we are not in the accept state (Y) the answer is no, repeated "a" does not take us to the accept state. Let's continue:
-From Z we can only reach Q, it does not matter if we get an "a" or "b". Assume we get another "a"
-When "Q" is reached there is no way to proceed to another state than Q, any sequence of letters "a" and "b" will always reach "Q"

I guess the DFA (3) accepts any sequence that is a repetition of "ab" followed by "a". Example: "aba" "ababa" "ababababa"

[zak100]

Hi,

Thanks for removing this fundamental confusion in a very good manner.

 

Zulfi.

 

 

 

[zak100]

Hi,

I have one more DFA and I have a confusion whether it accepts substring "aa" or "bb"  or not. It is given below:

 

 

 

 

 

 

 

 

 

I have a problem in understanding the state q4 and q5. If we give input a,b, randomly there is a possibility that we get two 'a's together or two 'b's together. Also if we get one 'a' then it can merge with previous 'a' comming from q3 to form "aa" which q5 would accept and we dont want. Same is the case with q4 in connection with a,b input. Somebody please guide me.

 

Zulfi.

Edited September 23, 2020 by zak100

[Ghideon]

1 hour ago, zak100 said:

I have one more DFA and I have a confusion whether it accepts substring "aa" or "bb"  or not. It is given below

The state q2 Can’t handle an ”a”, is that intended ? What is supposed to happen of you are in state q2 and receive an ”a”?

Same question applies to q3 and ”b”.

[zak100]

Hi,

Thanks a lot. 

q2 will get an "a", its fine. q2 will pass this "a" to q4 and now at q4 we have "ab" via q1q2q4. Now q4 can accept both 'a' and 'b'. Q4 is already having "ab" and if it gets "b", the accepted string would be "abb" which is not good.  I am saying that q4 should not accept 'a' or 'b' becase then we would accept string like "aa" or "bb" instead q4  should send the input  'a' or 'b' to garbage state. Is the arc with  a, b on q4 and q5 correct? I am saying its wrong because both q4 and a5 are accepting states and we don't want to accept a substring "aa" or "bb". But with arc having input a,b, both q4 and q5 can accept "aa" or "bb" which our DFA don't want. Please guide me.

 

Zulfi.

[Ghideon]

18 minutes ago, zak100 said:

q2 will get an "a", its fine. q2 will pass this "a" to q4

How? What arrow in the picture allow that transition? 
And if q2 gets a ”b” how do you select the next state?

 

Edited September 24, 2020 by Ghideon

[zak100]

Hi,

Ok but this is not a DFA because there is confusion.  Am I right? With input "b" at q2 we are going to both q3 and q4. So let's remove the transition from q2 to q3. Now start again from q1 with "a"  input to q1. At q2 we got a "b",so at q4 we have "ab". Now q4 is inputting a,b, what would happen? is q4 and q5 accepting "aa" and "bb" or not?

 

Zulfi.

[Ghideon]

9 minutes ago, zak100 said:

With input "b" at q2 we are going to both q3 and q4

As far as I can tell that is not allowed in a DFA*. Each state needs to have one and only one transition for each input. Q2 has no output state for "a" and two output states for "b". 

 

*) Formal definition: https://en.wikipedia.org/wiki/Deterministic_finite_automaton#Formal_definition