Vanligt språk

Ett vanligt språk ( vanlig uppsättning ) i teorin om formella språk  är en uppsättning ord som känner igen någon ändlig automat . Klassen med vanliga set är bekväm att studera som helhet, och de erhållna resultaten är tillämpliga på ett ganska brett utbud av formella språk.

Definition

Låta vara  ett ändligt alfabet . Vanliga språk i alfabetet är uppsättningar av ord som definieras av induktion enligt följande:

1. Den tomma uppsättningen ( ) är ett vanligt språk.
2. En uppsättning som bara består av en tom sträng ( ) är ett vanligt språk.
3. Uppsättningen som består av ett enbokstavsord ( , där ) är ett vanligt språk.
4. Om och  är vanliga språk, så är deras förening ( ), sammanlänkning ( ) och att ta Kleene-stjärnan ( ) också vanliga språk.
5. Det finns inga andra vanliga språk.

Anslutning mellan automater och vanliga språk

Kleenes teorem säger att klassen av reguljära språk är densamma som klassen av språk som känns igen av en finit automat . Detta betyder att för alla finita tillståndsmaskiner är den uppsättning ord som den tillåter ett vanligt språk. Och vice versa, för alla vanliga språk finns det en automat som tillåter ord från detta språk och bara dem.

En igenkännbar delmängd av en monoid

Detta koncept kan generaliseras till en godtycklig monoid. En delmängd L av en monoid M sägs vara igenkännbar över M om det finns en finit automat över M som accepterar L. En finit automat över M  är en automat som tar element från M som indata . Familjen av igenkännbara delmängder av en monoid M betecknas vanligtvis [1] .

Så om M  är en fri monoid över alfabetet , så är familjen helt enkelt en familj av vanliga språk .

Se även

• Stängd egendom för vanliga språk

Anteckningar

1. ↑ Jean-Eric Pin, Mathematical Foundations of Automata Theory Arkiverad 10 september 2014 på Wayback Machine , Kapitel IV: Igenkännbara och rationella uppsättningar