The hlavný rozdiel medzi regulárnym výrazom a bezkontextovou gramatikou je to, že regulárne výrazy pomáhajú popísať všetky reťazce regulárneho jazyka, zatiaľ čo bezkontextová gramatika pomáha definovať všetky možné reťazce bezkontextového jazyka.

Gramatika označuje syntaktické pravidlá pre konverzáciu v prirodzených jazykoch. Počítačová veda vo veľkej miere využíva teóriu formálnych jazykov. V roku 1956 Noam Chomsky poskytol matematický model gramatiky na písanie počítačových jazykov. Keď je možné z gramatiky odvodiť množinu všetkých reťazcov, hovorí sa, že jazyk je vygenerovaný z tejto gramatiky. Dva typy gramatiky sú pravidelná gramatika a bezkontextová gramatika. Každý jazyk, ktorý je možné opísať regulárnym výrazom, je regulárny jazyk. Bezkontextová gramatika je zovšeobecnením regulárneho výrazu. Regulárne výrazy je možné používať na písanie regulárnych jazykov a bezkontextovú gramatiku na písanie bezkontextovej gramatiky.

Regulárny výraz, gramatika bez kontextu

Čo je to regulárny výraz

Pravidelná gramatika generuje regulárne jazyky. Táto gramatika má jeden neterminál na ľavej strane a pravú stranu pozostávajúci z jedného terminálu alebo jedného terminálu, za ktorým nasleduje jeden nekoncový terminál. Výrobné pravidlo môže mať nasledujúce.

X -> a alebo X -> a Y

Kde X, Y ϵ N (nekoncový) a a ϵ T (terminál)

Regulárne výrazy pomáhajú písať pravidelnú gramatiku na opis regulárnych jazykov.

Regulárny výraz predstavuje určitý súbor reťazcov algebraickým spôsobom. Pri písaní regulárneho výrazu je potrebné dodržať niekoľko dôležitých pravidiel.

1. Terminálne symboly, nulový symbol a prázdny symbol sú regulárne výrazy.
2. Spojenie dvoch regulárnych výrazov je regulárny výraz.
3. Spojenie dvoch regulárnych výrazov je regulárny výraz.
4. Iterácia alebo uzavretie je regulárny výraz.

Regulárny výraz pre množinu {0, 1, 2} je nasledujúci.

R = 0 + 1 + 2

Množinu {abb, a, b, bba} môže reprezentovať nasledujúci regulárny výraz.

R = abb + a + b + bba

Uvažujme množinu, {ϵ, 0, 00, 000,…}

Ε je prázdny reťazec. Regulárny výraz je R = 0*. Toto predstavuje zatvorenie symbolu vrátane prázdneho symbolu.

V súprave {1, 11, 111, 1111,…..}

Regulárny výraz je R = 1 ^+. Toto + označuje zatvorenie symbolu bez prázdneho symbolu.

Čo je to bezkontextová gramatika

V teórii formálneho jazyka je Context Free Language (CFL) jazyk generovaný bezkontextovou gramatikou. Štyri parametre definujú bezkontextovú gramatiku (G).

G = {V, ∑, S, P}

V: Sada variabilných alebo nekoncových symbolov.

Poznámka: Sada symbolov terminálov

S: Začiatočný symbol

P: Výrobné pravidlo

Kontextová bezplatná gramatika má pre produkčné pravidlo nasledujúci formát.

A -> a kde a = {V, ∑}* a A ϵ V

Jeden príklad bezkontextovej gramatiky je nasledujúci. Každá inscenácia pozostáva z neterminálneho symbolu a regulárneho výrazu.

Na generovanie jazyka, ktorý generuje rovnaký počet a a b, je formát a b . Bezkontextová gramatika je nasledovná.

G = {(S, A), (a, b), (S -> aAb, A -> aAb | ϵ)}

Vzhľadom na symbol začiatku

S -> a A b

Aplikáciou A -> aAb

→ a a A b b

Opätovným použitím A -> aAb,

→ a a a A b b b

Použitím A -> ϵ (Tento symbol označuje prázdny reťazec)

→ a a a b b b

→ a ³ b ³

Keď vezmeme do úvahy výstup, počet a je rovný počtu b's. Má a b forma.

Vzťah medzi regulárnym výrazom a bezkontextovou gramatikou

Rozdiel medzi regulárnym výrazom a bezkontextovou gramatikou

Definícia

Regulárny výraz je pojem v teórii formálneho jazyka, ktorý je postupnosťou znakov, ktoré definujú vzor vyhľadávania. Kontextová voľná gramatika je typ formálnej gramatiky v teórii formálneho jazyka, čo je súbor produkčných pravidiel, ktoré opisujú všetky možné reťazce v danom formálnom jazyku.

Použitie

Regulárne výrazy pomáhajú reprezentovať určité sady reťazcov algebraickým spôsobom. Pomáha reprezentovať bežné jazyky. Bezkontextová gramatika pomáha definovať všetky možné reťazce bezkontextového jazyka.

Záver

Regulárny výraz je metóda porovnávania vzorov. Je to flexibilný spôsob poskytovania flexibilných a stručných prostriedkov na zosúladenie reťazcov textu. Definuje všetky reťazce v regulárnom jazyku. Na druhej strane bezkontextová gramatika umožňuje definovať všetky reťazce patriace do bezkontextového jazyka. Rozdiel medzi regulárnym výrazom a bezkontextovou gramatikou je v tom, že regulárne výrazy pomáhajú popísať všetky reťazce regulárneho jazyka, zatiaľ čo bezkontextová gramatika pomáha definovať všetky možné reťazce bezkontextového jazyka.

Referencia:

1. „Regulárne výrazy“. Www.tutorialspoint.com, Tutorials Point, 8. januára 2018, dostupné tu.2. „Úvod do bezkontextovej gramatiky.“ Www.tutorialspoint.com, Tutorials Point, 8. januára 2018, K dispozícii tu.

Obrázok so súhlasom:

1. „Toolbaricon RegEx“ od M0tty-vlastná práca (CC BY-SA 4.0) prostredníctvom Commons Wikimedia