Aké sú príklady pravidelných jazykov a ako sa definujú v kontextovej teórii formálneho jazyka?

Dobre, preskúmajme pravidelné jazyky s príkladmi a ich definíciami v teórii formálneho jazyka.

Čo sú to pravidelné jazyky?

V oblasti teórie formálneho jazyka je pravidelný jazyk jazyk (súbor reťazcov nad danou abecedou), ktorý možno opísať:

* regulárne výrazy: Vzor, ktorý definuje súbor reťazcov.

* Deterministické konečné automaty (DFA): Stroj, ktorý číta vstupný symbol naraz a prechody medzi stavmi na základe vstupu. Prijíma alebo odmieta vstup na základe konečného stavu.

* Neterministické konečné automaty (NFA): Podobne ako v prípade DFA, ale umožňujú viac možných prechodov zo stavu pre daný vstupný symbol (alebo dokonca prechody bez toho, aby ste si prečítali akýkoľvek vstup).

* Pravidelné gramatiky: Typ formálnej gramatiky, v ktorej majú pravidlá výroby špecifickú formu.

Tieto štyri reprezentácie sú rovnocenné. Ak môžete s jedným z nich definovať jazyk, môžete ho definovať so všetkými. Toto je základná veta vo formálnom jazykovom teórii.

Príklady bežných jazykov

Tu je niekoľko príkladov spolu s tým, ako ich možno definovať pomocou vyššie uvedených metód:

1. Jazyk všetkých reťazcov nad {0, 1}, ktorý začína '1'.

* regulárny výraz: `1 (0 | 1)*` (alebo `1 [01]*`)

* `1` na začiatku zodpovedá požadovanej '1'.

* `(0 | 1)` znamená "buď 0 alebo 1".

* `*` znamená „nula alebo viac výskytov predchádzajúcej skupiny.“

* dfa:

`` `

0 1

-> Q0 Q1 Q1 (Q0 je stav Štart)

Q1 Q1 Q1 (Q1 je prijímajúci stav)

`` `

* `Q0` je počiatočný stav. Ak vstup začína '1', prechádza do prijímacieho stavu „Q1`. Ak sa začne `0`, presunie sa do nekvalitného (mŕtveho) stavu.

* `Q1` je prijímajúci stav. Akonáhle dosiahne tento stav, zostane v ňom a prijíma akýkoľvek ďalší vstup.

* nfa: NFA môže byť postavená podobne, ale môže mať alternatívnu cestu zo štartovacieho stavu.

* Pravidelná gramatika: (Pravicová lineárna)

`` `

S -> 1A

A -> 0A | 1A | ε

`` `

* `S` je symbol štartu.

* `A` generuje akúkoľvek kombináciu 0S a 1S, vrátane prázdneho reťazca (ε).

2.

* regulárny výraz: `(a | b)*aba (a | b)*` (alebo `[ab]*aba [ab]*`)

* `(a | b)*` Zhoduje sa s akoukoľvek sekvenciou 'A a' B (nula alebo viac).

* `ABA` zodpovedá požadovanému podrezetu.

* dfa: Tento DFA bude mať štáty na sledovanie pokroku v porovnaní „ABA“:

`` `

b

-> Q0 Q1 Q0

Q1 Q1 Q2

Q2 Q1 Q0

Q3 Q3 Q3 (Q3 je prijímajúci stav)

`` `

* `Q0`:Počiatočný stav. Predstavuje, že sme nevideli žiadnu časť „ABA“.

* `Q1`:predstavuje, že sme videli„ A “.

* `Q2`:predstavuje, že sme videli„ AB “.

* `Q3`:predstavuje, že sme videli„ ABA “(prijímajúci stav). Akonáhle je v `Q3`, akýkoľvek ďalší vstup si udržuje v` Q3`.

* nfa: NFA môže byť jednoduchšie zostaviť pre tento jazyk. Môže to „uhádnuť“, keď by sa mohol začať podrestík „ABA“.

* Pravidelná gramatika:

`` `

S -> ako | BS | aa

A -> bb

B -> ac

C -> AC | BC | ε

`` `

3.

* regulárny výraz: `1*(01*01*)*`

* `1*`:nula alebo viac

*`01*01*`:To znamená, že reťazec by mal mať párne číslo 0 s, pretože po ktoromkoľvek 0 musí nasledovať `1*01*`, takže je spárovaný.

* dfa:

`` `

0 1

-> Q0 Q1 Q0 (Q0 je stav začiatku a prijímania)

Q1 Q0 Q1 (Q1 je stav, ktorý nie je akceptovaný)

`` `

* `Q0`:párne číslo 0S (štart a prijímanie stavu).

* `Q1`:nepárne číslo 0 s.

* nfa: Je možné skonštruovať NFA, ale DFA je často priamejšia reprezentácia.

* Pravidelná gramatika:

`` `

S -> 1S | 0A | ε

A -> 1A | 0s

`` `

4. Jazyk pozostávajúci iba z reťazca „ahoj“.

* regulárny výraz: „Dobrý deň`

* dfa:

`` `

h e l l o

-> Q0 Q1 - - - (Q0 je štartovací stav)

Q1 - Q2 - - - -

Q2 - - Q3 - -

Q3 - - - Q4 -

Q4 - - - - Q5

Q5 - - - - (Q5 je prijímajúci stav)

`` `

* Pravidelná gramatika:

`` `

S -> ha

A -> eb

B -> LC

C -> ld

D -> o

`` `

Príklady jazykov, ktoré nie sú pravidelné

Tieto jazyky * nemôžu byť reprezentované regulárnymi výrazmi, DFA, NFA alebo pravidelnými gramatikami. Vyžadujú silnejšie formalizmy, ako sú gramatiky bez kontextov alebo Turing stroje.

1. Jazyk reťazcov s rovnakým počtom „A a“ B:{ε, ab, ba, aabb, Abab, baba, bbaa, ...}

2. {ε, a, b, aa, bb, aba, bab, abba, ...}

3. Jazyk {a

n B

n | n> =0} :Stringy s `n` 'A nasledujú` n`' B (napr. Ε, ​​AB, Aabb, AAABBB, ...). Toto je klasický príklad, ktorý sa často používa na preukázanie obmedzení bežných jazykov.

4. Jazyk {a

n B

m C n | n, m> =0} :Stringy s `n` A's, nasledované` m` b's a `n` c's. To je neregulárne.

Prečo tieto jazyky nie sú pravidelné?

Kľúčovým obmedzením bežných jazykov je ich neschopnosť „počítať“ alebo „pamätať“ na ľubovoľné množstvo informácií. DFA, NFA alebo regulárny výraz má konečný počet stavov alebo symbolov. Rozpoznať jazyky ako {a

n B

n }, museli by ste sledovať počet „A, ktoré ste videli, aby ste sa uistili, že existuje rovnaký počet B. Konečný automat nemá pamäťovú kapacitu na to pre ľubovoľne veľkú `n`. Táto intuícia je formalizovaná *čerpaním Lemmy pre bežné jazyky *, výkonný nástroj na preukázanie toho, že jazyk nie je *pravidelný.

v súhrne

Pravidelné jazyky sú základnou triedou jazykov v teórii formálneho jazyka. Dajú sa ľahko definovať a implementovať, vďaka čomu sú užitočné pre mnoho praktických aplikácií (napr. Lexikálna analýza v kompilátoroch, porovnávanie vzorov v textových editoroch, smerovanie siete). Majú však obmedzenia a zložitejšie jazyky si vyžadujú silnejšie formalizmy.

• Predchádzajúca strana: Aké sú príklady neurčiacich rozpoznateľných jazykov a ako sa líšia od Turingových jazykov? 
• Ďalšia strana: Aké sú výhody použitia normalizovaných čísel služieb v počítači?