Kvocient automat - Quotient automaton - Wikipedia

v počítačová věda, zejména v teorie formálního jazyka, a kvocientový automat lze získat z daného nedeterministický konečný automat připojením se k některým jeho státům. Kvocient rozpozná nadmnožinu daného automatu; v některých případech řešeno Věta Myhill – Nerode, oba jazyky jsou stejné.

Formální definice

A (nedeterministické) konečný automat je pětinásobný A = ⟨Σ, S, s₀, δ, S_FWhere, kde:

• Σ je vstup abeceda (konečný, neprázdný soubor symbolů),
• S je konečná, neprázdná množina stavů,
• s₀ je počáteční stav, prvek S,
• δ je přechod státu vztah: δ ⊆ S × Σ × S, a
• S_F je sada konečných stavů, (případně prázdná) podmnožina S.^{[1][poznámka 1]}

A tětiva A₁...A_n ∈ Σ^* je rozpoznán A pokud existují státy s₁, ..., s_n ∈ S takové, že ⟨s_i-1,A_i,s_i⟩ ∈ δ pro i=1,...,n, a s_n ∈ S_F. Sada všech řetězců rozpoznaných A se nazývá Jazyk uznán A; označuje se jako L(A).

Pro vztah ekvivalence ≈ na scéně S z AStátů, kvocientový automat A/_≈ = ⟨Σ, S/_≈, [s₀], δ/_≈, S_F/_≈⟩ Je definováno^[2]:5

• vstupní abeceda Σ je stejný jako u A,
• stát nastaven S/_≈ být souborem všech třídy ekvivalence států z S,
• počáteční stav [s₀] je třída ekvivalence APočáteční stav,
• vztah státu a přechodu δ/_≈ je definován δ/_≈([s],A,[t]) pokud δ(s,A,t) pro některé s ∈ [s] a t ∈ [t], a
• množina konečných stavů S_F/_≈ je souborem všech tříd ekvivalence konečných stavů z S_F.

Proces výpočtu A/_≈ je také nazýván factoring A o ≈.

Příklad

Kvocientové příklady

	Automat diagram	Uznáno Jazyk	Je podíl z
			A podle	B podle	C podle
A:		1+10+100
B:		1*+1*0+1*00	a≈b
C:		1*0*	a≈b, c≈d	c≈d
D:		(0+1)*	a≈b≈c≈d	a≈c≈d	a≈c

Například automat A zobrazené v prvním řádku tabulky^{[poznámka 2]} je formálně definován

• Σ^A = {0,1},
• S^A = {a, b, c, d},
• s^A
  ₀ = a,
• δ^A = {⟨A, 1, b⟩, ⟨b, 0, c⟩, ⟨c, 0, d⟩} a
• S^A
  _F = {b, c, d}.

Rozpoznává konečnou množinu řetězců {1, 10, 100}; tuto sadu lze označit také regulární výraz "1+10+100".

Vztah (≈) = {⟨a, a⟩, ⟨a, b⟩, ⟨b, a⟩, ⟨b, b⟩, ⟨c, c⟩, ⟨c, d⟩, ⟨d, c⟩, ⟨ d, d⟩}, stručněji označeno jako a≈b, c≈d, je ekvivalenční vztah na množině {a, b, c, d} automatu AStavy. Vytvoření podílu A tímto vztahem vznikne automat C ve třetím řádku tabulky; je formálně definován

• Σ^C = {0,1},
• S^C = {a, c},^{[Poznámka 3]}
• s^C
  ₀ = a,
• δ^C = {⟨A, 1, a⟩, ⟨a, 0, c⟩, ⟨c, 0, c⟩} a
• S^C
  _F = {a, c}.

Rozpoznává konečnou množinu všech řetězců složených z libovolně mnoha 1 s, následovaných libovolně mnoha 0, tj. {Ε, 1, 10, 100, 1000, ..., 11, 110, 1100, 11000, ..., 111, ...}; tuto množinu lze označit také regulárním výrazem „1^*0^*".Neformálně, C lze myslet na výsledek A lepením stavu a do stavu b a lepením stavu c do stavu d.

V tabulce jsou uvedeny některé kvocientové vztahy, například B = A/_a≈b, a D = C/_a≈c.

Vlastnosti

• Pro každý automat A a každý vztah ekvivalence ≈ na jeho stavech nastaven, L(A/_≈) je nadmnožinou (nebo rovno) L(A).^[2]:6
• Vzhledem k omezenému automatu A přes nějakou abecedu Σ, lze definovat relaci ekvivalence ≈ Σ^* podle X ≈ y pokud ∀ z ∈ Σ^*: xz ∈ L(A) ↔ yz ∈ L(A). Podle Věta Myhill – Nerode, A/_≈ je deterministický automat, který rozpoznává stejný jazyk jako A.^[1]:65–66 V důsledku toho je podíl z A každým upřesnění of ≈ také rozpoznává stejný jazyk jako A.

Viz také

• Kvocientová skupina
• Kategorie kvocientu

Poznámky

Reference