patternMinor
Designing a DFA that accepts strings such that nth character from last satisfies condition
Viewed 0 times
suchdfaacceptsnthlastconditiondesigningcharacterthatfrom
Problem
This is a homework question, so I am only looking for hints.
I got a question in an assignment which states :
Design a DFA that accepts strings having 1 as the 4th character from the end, on the alphabet {0,1}
I have been at this for a few hours now, and I think that designing such a DFA is not possible. However, I am not sure how to move forward in this direction to write up a somewhat formal proof.
So, what should I try to do to prove or disprove my hypothesis?
I got a question in an assignment which states :
Design a DFA that accepts strings having 1 as the 4th character from the end, on the alphabet {0,1}
I have been at this for a few hours now, and I think that designing such a DFA is not possible. However, I am not sure how to move forward in this direction to write up a somewhat formal proof.
So, what should I try to do to prove or disprove my hypothesis?
Solution
Hint: Your language can be described by the regular expression $\{0,1\}^*1\{0,1\}^3$.
Another hint: Your DFA can remember the last $4$ characters (and maintain that information). You will also need states to handle the case in which less than $4$ characters have been seen so far.
Another hint: Your DFA can remember the last $4$ characters (and maintain that information). You will also need states to handle the case in which less than $4$ characters have been seen so far.
Context
StackExchange Computer Science Q#14008, answer score: 7
Revisions (0)
No revisions yet.