De grootste verschil tussen reguliere expressie en contextvrije grammatica is dat de reguliere expressies helpen om alle strings van een reguliere taal te beschrijven, terwijl de contextvrije grammatica helpt om alle mogelijke strings van een contextvrije taal te definiëren.

Grammatica geeft syntactische regels aan voor conversatie in natuurlijke talen. Informatica maakt in grote mate gebruik van de theorie van formele talen. In het jaar 1956 gaf Noam Chomsky een wiskundig model van grammatica voor het schrijven van computertalen. Wanneer het mogelijk is om een ​​verzameling van alle strings uit een grammatica af te leiden, wordt gezegd dat de taal uit die grammatica wordt gegenereerd. Twee soorten grammatica zijn reguliere grammatica en contextvrije grammatica. Elke taal die door een reguliere expressie kan worden beschreven, is een reguliere taal. Contextvrije grammatica is een veralgemening van reguliere expressie. Het is mogelijk om reguliere expressies te gebruiken om reguliere talen te schrijven en contextvrije grammatica om contextvrije grammatica te schrijven.

Reguliere expressie, contextvrije grammatica

Wat is reguliere expressie?

De reguliere grammatica genereert reguliere talen. Deze grammatica heeft een enkele niet-terminal aan de linkerkant en een rechterkant die bestaat uit een enkele terminal of een enkele terminal gevolgd door een enkele niet-terminal. Het kan als volgt een productieregel hebben.

X -> a of X -> een Y

Waar X, Y ϵ N (niet-terminaal) en a ϵ T (terminaal)

Reguliere expressies helpen bij het schrijven van reguliere grammatica om reguliere talen te beschrijven.

Een reguliere expressie vertegenwoordigt een bepaalde reeks strings op een algebraïsche manier. Enkele belangrijke regels die u moet volgen bij het schrijven van een reguliere expressie zijn de volgende.

1. De terminalsymbolen, het nulsymbool en het lege symbool zijn reguliere expressies.
2. De vereniging van twee reguliere expressies is een reguliere expressie.
3. De aaneenschakeling van twee reguliere expressies is een reguliere expressie.
4. Iteratie of sluiting is een reguliere expressie.

De reguliere expressie voor de set {0, 1, 2} is als volgt.

R = 0 + 1+2

De verzameling {abb, a, b, bba} kan worden weergegeven door de volgende reguliere expressie.

R = abb + a +b + bba

Beschouw de verzameling, {ϵ, 0, 00, 000, …}

De ϵ is de lege string. De reguliere expressie is R = 0*. Dit vertegenwoordigt de sluiting van het symbool inclusief het lege symbool.

In de verzameling {1, 11, 111, 1111, …..}

De reguliere expressie is R = 1 ^+. Deze + geeft de sluiting van een symbool aan, exclusief het lege symbool.

Wat is contextvrije grammatica

In de formele taaltheorie is Context Free Language (CFL) een taal die wordt gegenereerd door Context Free Grammar. Vier parameters definiëren contextvrije grammatica (G).

G= {V, ∑, S, P}

V: Set van variabele of niet-terminale symbolen.

∑: Set terminalsymbolen

S: Startsymbool

P: Productieregel

Context Free Grammar heeft het volgende formaat voor productieregel.

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

Een voorbeeld van contextvrije grammatica is als volgt. Elke productie bestaat uit een niet-terminaal symbool en een reguliere expressie.

Voor het genereren van een taal die een gelijk aantal a's en b's genereert in het formaat a B . De contextvrije grammatica is als volgt.

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

Gezien het startsymbool,

S – > a A b

Door A -> aAb. toe te passen

→ a a A b b

Door A -> aAb opnieuw toe te passen,

→ a a a A b b b

Door A -> ϵ toe te passen (Dit symbool geeft een lege string aan)

→ a a b b b

→ een ³ B ³

Bij het beschouwen van de output is het aantal a's gelijk aan het aantal b's. Het heeft de a B formulier.

Relatie tussen reguliere expressie en contextvrije grammatica

Verschil tussen reguliere expressie en contextvrije grammatica

Definitie

Een reguliere expressie is een concept in de formele taaltheorie dat een reeks karakters is die een zoekpatroon definiëren. Contextvrije grammatica is een vorm van formele grammatica in de formele taaltheorie, een verzameling productieregels die alle mogelijke strings in een bepaalde formele taal beschrijven.

Gebruik

Reguliere expressies helpen om bepaalde reeksen strings op een algebraïsche manier weer te geven. Het helpt om reguliere talen weer te geven. Contextvrije grammatica helpt om alle mogelijke strings van een contextvrije taal te definiëren.

Conclusie

Een reguliere expressie is een methode om patronen te matchen. Het is een flexibele methode om een ​​flexibele en beknopte manier te bieden om reeksen tekst op elkaar af te stemmen. Het definieert alle strings in de reguliere taal. Aan de andere kant maakt contextvrije grammatica het mogelijk om alle strings te definiëren die tot een contextvrije taal behoren. Het verschil tussen reguliere expressie en contextvrije grammatica is dat de reguliere expressies helpen om alle strings van een reguliere taal te beschrijven, terwijl de contextvrije grammatica helpt om alle mogelijke strings van een contextvrije taal te definiëren.

Verwijzing:

1. "Regelmatige expressies." Www.tutorialspoint.com, Tutorials Point, 8 januari 2018, hier beschikbaar.2. "Contextvrije grammatica-introductie." Www.tutorialspoint.com, Tutorials Point, 8 januari 2018, hier beschikbaar.

Afbeelding met dank aan:

1. "Toolbaricon RegEx" door M0tty - Eigen werk (CC BY-SA 4.0) via Commons Wikimedia