gramatica Regular - ea
Stabilirea setului de reguli
gramatica regulată poate fi definită printr-un set de reguli ca gramatica regulată stânga sau la dreapta.
gramatica regulată dreapta - toate regulile pot fi într-una din următoarele forme:
gramatica regulată stânga - toate regulile pot fi într-una din următoarele forme:
- capace (A. B) denota non-terminale ale multitudinii de N
- litere mici (a. b) denotă bornele pluralității Σ
- ε - string gol, adică Lungimea liniei 0
Clasele de dreapta și la stânga Gramatici regulate sunt echivalente - suficiente pentru a defini în mod individual toate limbile obișnuite. Orice gramatica regulată poate fi convertit de la stânga la dreapta și invers.
Dreptul gramatica regulată G. predeterminate N =, Σ =, P este alcătuit din următoarele reguli:
S → aS S → bA A → ε A → cA
și S este simbolul de pornire. Această gramatică descrie aceeași limbă ca și expresia regulată a * bc *.
îngustimea
Orice gramatica de context poate fi ușor transformată într-o formă în care normele constau numai din stânga-dreapta regulată și-regulat (pentru gramatici independente de context este permisă prezența ambele în același timp). Prin urmare, astfel de gramatici poate exprima toate limbile de context. Gramatici regulate pot conține fie o reguli-stânga regulat, sau de dreapta regulat, dar nu ambele simultan. Prin urmare, ele pot descrie un subset limitat de limbi numite limbaje regulate.
De exemplu, un context liber siruri de limbaj aibi tip gramatical definit G. unde N =, Σ =, P este format din reguli
S → aA A → D S → ε
și S este simbolul de pornire. Rețineți că această gramatica conține atât reguli stânga-dreapta regulate și-regulate, și, prin urmare, nu este regulat.
literatură
Vezi ce „gramatica regulată“ în alte dicționare:
Ierarhia Chomsky - Chomsky clasificarea ierarhie a limbilor formale și gramatici formale, în conformitate cu care acestea sunt împărțite în 4 tipuri în funcție de complexitatea lor condiționată. Propus de profesorul MIT lingvistul Noam Chomsky. ... ... Wikipedia
gramatica Regular - în informatică, o gramatică regulată este o gramatica formală a tipului 3 de ierarhia Chomsky. Gramatici regulate defini exact toate limbile obișnuite, și, prin urmare, este echivalent cu automate finite și expresii regulate. Gramatici regulate ... ... Wikipedia
Gramatica formală - gramatica formală sau o gramatică în teorie limbaj formal un mod de a descrie un limbaj formal, și anume alocarea unui subset al setului de toate cuvintele unui alfavita finit. Distinge generarea și recunoașterea (sau ... ... Wikipedia
Turing completitudinea - În interpret teoria calculabilitate (mai mulți membri ai calculat) este Turing completă dacă este posibil să se pună în aplicare orice funcție calculabil. Cu alte cuvinte, pentru orice funcție calculabil există calculează elementul său (de exemplu, ... ... Wikipedia
- Stochastic gramatica de context. Dzhessi Rassel. Această carte va fi făcută în conformitate cu comanda pe tehnologia de imprimare Tehnologie-on-Demand. Conținutul de calitate înaltă prin articole wikipedia! Stochastic context-free gramatica (SCS, ... Read More Cumpără pentru 854 de ruble
- Ca eu sunt un elev de limbă. Note Poliglot. Lomb Kato. Kato Lomb, care știa 16 limbi, se crede că împărțirea oamenilor în și a celor cu „abilități speciale de limbi străine“ greșit. Această carte - chintesența experiențele sale, reflecții Polyglot isovety: ... Citește mai mult Vand pentru 743 ruble
- Ca eu sunt un elev de limbă. Note Poliglot. Lomb K. Această carte - expoziție vie și directă a poliglotul opinii și unul dintre primii interpreți ai lumii pe diferite sisteme lingvistice. Baza acestei Carti- experiență de învățare propriu ... Citește mai mult Vand pentru 599 de ruble