NFA for Strings Starting with A or BB

NFA for strings starting with a or bb

This epsilon-NFA illustrates a language with alternative prefixes. It reads the first symbol at q0. An a moves to qa, while a b moves to q1, which needs a second b to reach qb. The two successful branches then merge into qf by epsilon, where the machine can consume any remaining symbols. The epsilon transitions mean the required prefix itself is enough for acceptance; no extra input is needed before qf. The drawing shows that acceptance depends on the beginning of the input rather than its end. Prefix languages are common in token recognition, command parsing and protocol dispatch, where the first few symbols choose a valid form.

Type Diagramme d’étatsNorme OMG UML 2.5.1 §14 + Harel (1987) statechartMoteur schematex-stateMis à jour 24/09/2026

La demande

“Draw an epsilon-NFA over a and b that accepts strings beginning with a or bb: q0 goes to qa on a or q1 on b, q1 goes to qb on b, and either successful branch reaches accepting qf by epsilon, which loops on a and b.”

Essayez ensuiteReplace the epsilon transitions to qf with transitions that consume c.Add a branch that accepts strings starting with baa.

Ce que contient ce dessin

Comprenez les décisions qui le sous-tendent.

01Branching prefix

q0 separates the a and bb alternatives.

02Successful merge

qa and qb lead to one accepting continuation.

03Suffix loop

qf accepts arbitrary remaining input after a valid prefix.

Use a branch-and-merge automaton for a language defined by several allowed starting patterns.

Voir tous les modèles de diagramme d’états →

FAQ

Questions fréquentes

What prefixes does the machine recognize?

It recognizes inputs whose beginning is a or bb, followed by a binary suffix.

Why is there a separate q1 state?

It records that the first b has been read and a second b is required.

Can the branches share one final state?

Yes. Both branches express valid prefixes, so they can merge before consuming the rest of the input.