NFA for Binary Strings Containing 101

NFA for binary strings containing 101

This NFA accepts binary strings that contain 101 as a substring. State q0 reads through any prefix and loops on both symbols. On a 1, it can also branch to q1 and treat that symbol as the start of a possible match. The path q1 to q2 to q3 then requires 0 followed by 1. Once q3 is reached, it loops on either symbol because the required substring has already been found. Nondeterminism matters when possible matches overlap: the q0 loop can continue scanning while another path tests a particular 1. This same pattern adapts naturally to searching for another fixed word or protocol marker.

유형 상태 다이어그램표준 OMG UML 2.5.1 §14 + Harel (1987) statechart엔진 schematex-state업데이트됨 2026. 9. 24.

요청 내용

“Draw an NFA over 0 and 1 that accepts strings containing 101: q0 loops on both symbols and can start a match on 1, followed by 0 to q2 and 1 to accepting q3, which loops on both symbols.”

그렇다면Change the sought substring from 101 to 110.Remove the loops from q3 so the machine accepts only strings ending in 101.

이 도면에 담긴 내용

그 이면의 의사결정을 읽어 보세요.

01Scanning loop

q0 can skip an arbitrary prefix.

02Nondeterministic start

a 1 can be ignored or treated as the first symbol of 101.

03Accepting loop

q3 permits any suffix after a completed match.

Use this structure to recognize whether a short token occurs anywhere in a stream.

모든 상태 다이어그램 템플릿 보기 →

자주 묻는 질문

Why is q3 an accepting state with loops?

After finding 101, any remaining binary suffix still belongs to the language.

Can overlapping matches be handled?

Yes. Nondeterministic paths let the automaton test different starting positions at once.

Does 1001 get accepted?

No. It does not contain 101 as consecutive symbols.