Jump to content

understanding DFA


zak100

Recommended Posts

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.

undertsanding1.png

 

 

 

Similalry the following one:

 

 

 

understanding3.thumb.JPG.08cf62b520ad035e6f5a07f4d4ab2c19.JPG

 

 

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 by zak100
Link to comment
Share on other sites

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?

undertsanding1.png

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 by fiveworlds
Link to comment
Share on other sites

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.

 

Link to comment
Share on other sites

Hi,

What is the difference between (3) and (4)?understanding4_3.png.cee2aeb2c05b7466c88570a38c33c050.png

 

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

understanding4_4.png.947d434dfb27289ccc5a50ab6b69809d.png

 

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

Somebody please guide me.

 

Zulfi.

 

 

 

Link to comment
Share on other sites

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?

a-a.png.8a7a117e0f877a40933294ecb3aa03c9.png

 

 

Link to comment
Share on other sites

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?

ad.png.130d51d1530e7344d32cf5cc44333f10.png

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"

Link to comment
Share on other sites

Hi,

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

 

 

 

 

 

 

 

Not sure whether it accept aa or bb.png

 

 

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 by zak100
Link to comment
Share on other sites

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

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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 by Ghideon
Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.