Almindeligt sprog

Et regulært sprog ( regulært sæt ) i teorien om formelle sprog  er et sæt ord , der genkender en eller anden endelig automat . Klassen med almindelige sæt er praktisk at studere som en helhed, og de opnåede resultater kan anvendes på en temmelig bred vifte af formelle sprog.

Definition

Lad være  et endeligt alfabet . Almindelige sprog i alfabetet er sæt af ord defineret ved induktion som følger:

1. Det tomme sæt ( ) er et almindeligt sprog.
2. Et sæt, der kun består af én tom streng ( ) er et almindeligt sprog.
3. Sættet bestående af et enkeltbogstavsord ( , hvor ) er et almindeligt sprog.
4. Hvis og  er regulære sprog, så er deres forening ( ), sammenkædning ( ) og at tage Kleene-stjernen ( ) også regulære sprog.
5. Der er ingen andre regulære sprog.

Forbindelse mellem automater og almindelige sprog

Kleenes teorem siger, at klassen af ​​regulære sprog er den samme som klassen af ​​sprog, der genkendes af en endelig automat . Dette betyder, at for enhver finite state-maskine er det sæt af ord, som det tillader, et regulært sprog. Og omvendt, for ethvert almindeligt sprog er der en automat, der tillader ord fra dette sprog og kun dem.

En genkendelig delmængde af en monoid

Dette koncept kan generaliseres til en vilkårlig monoid. En delmængde L af en monoid M siges at være genkendelig over M , hvis der eksisterer en endelig automat over M , der accepterer L. En endelig automat over M  er en automat, der tager elementer fra M som input . Familien af ​​genkendelige delmængder af en monoid M betegnes normalt [1] .

Så hvis M  er en fri monoid over alfabetet , så er familien simpelthen en familie af regulære sprog .

Se også

• Lukket ejendom for regulære sprog

Noter

1. ↑ Jean-Eric Pin, Mathematical Foundations of Automata Theory Arkiveret 10. september 2014 på Wayback Machine , Kapitel IV: Genkendelige og rationelle sæt