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.

Tipo Diagramma degli statiStandard OMG UML 2.5.1 §14 + Harel (1987) statechartMotore schematex-stateAggiornato 24/09/2026

La richiesta

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

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

Cosa contiene questo disegno

Leggi le decisioni che ne stanno alla base.

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.

Sfoglia tutti i modelli di tipo diagramma degli stati →

FAQ

Domande frequenti

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.