TransWikia.com

DFA for every run of a's=2 or 3

Computer Science Asked by matt mowris on December 17, 2021

I am trying to create a dfa for L={w: every run of a’s has length either two or three}

this is my attempt at the solution..i feel like I am missing something..?

enter image description here

3 Answers

5 states: E = Error detected, and S0 to S3 = No error detected, input ends in 0, 1, 2, or 3 a’s. S0, S2 and S3 are accepting.

An a moves from S0, S1, S2 to S1, S2, S3, and from S3 or E To E. b moves from S0, S2 or S3 to S0, and from S1 or E to E.

Close to yours, but S0 is accepting, and b in state S1 goes to the error state.

Answered by gnasher729 on December 17, 2021

I came across this question in Peter Linz' Introduction to Formal Languages and Automata. There it is mentioned that "a run in a string is a substring of length atleast 2". Hence a single $a$ is not a run of $a$. Moreover, every run of $a$'s is either of length two or three can be read as "if there exists a run of $a$'s , then it should be either of length two or three". Hence 0 or 1 $a$ should also be accepted. Your DFA is right except for the fact that $q_0$ and $q_1$ will also be accepting states. $baabbabbab in L$ because it has run of $a$'s of length two.

Answered by Ayush on December 17, 2021

Yes, there is something wrong. In your comment you stated that you feel that it should be accepting $baabbabbab$. You are wrong about this.

The language you want is $L={w in {a,b}^* | w = ((aa|aaa|epsilon)b)^*(aa|aaa|epsilon)}$

Clearly, $baabbabbab notin L$.

Regarding your DFA, I have some excellent news but you'll quiesce in your pants about it. In fact, your DFA accepts any string that ends in a run of a's of length 2 or 3 and contains no runs of length 4 i.e. $L(<your DFA>) = {w in {a,b}^* | w= (ab|aab|aaab|b)^*(aa|aaa)}$.

HINT

State $q_1$ in your proposed DFA, on $b$, should go to a halting state.

Answered by d'alar'cop on December 17, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP