Differenza tra espressione regolare e grammatica libera dal contesto
Share
Il differenza principale tra l'espressione regolare e la grammatica libera dal contesto è che il le espressioni regolari aiutano a descrivere tutte le stringhe di una lingua normale mentre la grammatica libera dal contesto aiuta a definire tutte le possibili stringhe di un linguaggio libero dal contesto.
La grammatica indica le regole sintattiche per la conversazione in lingue naturali. L'informatica utilizza in larga misura la teoria dei linguaggi formali. Nell'anno 1956, Noam Chomsky diede un modello matematico di grammatica per scrivere i linguaggi del computer. Quando è possibile derivare un insieme di tutte le stringhe da una grammatica, si dice che la lingua sia generata da quella grammatica. Due tipi di grammatica sono grammatica regolare e grammatica libera dal contesto. Qualsiasi lingua che possa essere descritta da un'espressione regolare è una lingua normale. La grammatica libera dal contesto è una generalizzazione dell'espressione regolare. È possibile utilizzare espressioni regolari per scrivere lingue regolari e grammatica libera dal contesto per scrivere la grammatica senza contesto.
Aree chiave coperte
1. Cos'è l'espressione regolare
- Definizione, esempi
2. Cos'è la grammatica Context Free
- Definizione, esempi
3. Relazione tra espressione regolare e grammatica libera dal contesto
- Schema dell'associazione
4. Differenza tra espressione regolare e grammatica libera dal contesto
- Confronto tra le principali differenze
Parole chiave
Espressione regolare, grammatica libera dal contesto
Cos'è l'espressione regolare
La grammatica regolare genera linguaggi regolari. Questa grammatica ha un singolo non-terminale sul lato sinistro e un lato destro costituito da un singolo terminale o singolo terminale seguito da un singolo non-terminale. Può avere una regola di produzione come segue.
X -> a o X -> a Y
Dove X, Y ε N (non terminale) e a ε T (terminale)
Le espressioni regolari aiutano a scrivere una grammatica regolare per descrivere le lingue regolari.
Un'espressione regolare rappresenta un certo insieme di stringhe in modo algebrico. Alcune regole importanti da seguire quando si scrive un'espressione regolare sono le seguenti.
- I simboli del terminale, il simbolo nullo e il simbolo vuoto sono espressioni regolari.
- L'unione di due espressioni regolari è un'espressione regolare.
- La concatenazione di due espressioni regolari è un'espressione regolare.
- L'iterazione o chiusura è un'espressione regolare.
L'espressione regolare dell'insieme 0,1,2 è la seguente.
R = 0 + 1 + 2
L'insieme abb, a, b, bba può essere rappresentato dalla seguente espressione regolare.
R = abb + a + b + bba
Considera l'insieme, ε, 0, 00, 000, ...
Il ε è la stringa vuota. L'espressione regolare è R = 0 *. Questo rappresenta la chiusura del simbolo incluso il simbolo vuoto.
Nell'insieme 1, 11, 111, 1111, ...
L'espressione regolare è R = 1 +. Questo + indica la chiusura di un simbolo escludendo il simbolo vuoto.
Cos'è la grammatica Context Free
Nella teoria del linguaggio formale, Context Free Language (CFL) è un linguaggio generato da Context Free Grammar. Quattro parametri definiscono la grammatica free-context (G).
G = V, Σ, S, P
V: Set di simboli variabili o non terminali.
Σ: set di simboli del terminale
S: Inizia simbolo
P: Regola di produzione
La grammatica Free Context ha il seguente formato per la regola di produzione.
A -> a dove a = V, Σ * e A ε V
Un esempio di Context Free Grammar è il seguente. Ogni produzione consiste in un simbolo non terminale e un'espressione regolare.
Per generare un linguaggio che genera un numero uguale di a e b's è nel formato di anBn. La grammatica context free è la seguente.
G = (S, A), (a, b), (S -> aAb, A -> aAb | ε)
Considerando il simbolo di partenza,
S -> a A b
Applicando A -> aAb
→ a a A b b
Applicando di nuovo A -> aAb,
→ a a a A b b b
Applicando A -> ε (Questo simbolo indica una stringa vuota)
→ a a a b b b
→ a 3 B 3
Quando si considera l'output, il numero di a è uguale al numero di b. Ha l'an Bn modulo.
Relazione tra espressione regolare e grammatica libera dal contesto
- La grammatica libera dal contesto è una generalizzazione delle espressioni regolari.
Differenza tra espressione regolare e grammatica libera dal contesto
Definizione
Un'espressione regolare è un concetto nella teoria del linguaggio formale che è una sequenza di caratteri che definisce un modello di ricerca. La grammatica libera di contesto è un tipo di grammatica formale nella teoria del linguaggio formale, che è un insieme di regole di produzione che descrivono tutte le possibili stringhe in un determinato linguaggio formale.
uso
Le espressioni regolari aiutano a rappresentare determinati insiemi di stringhe in modo algebrico. Aiuta a rappresentare le lingue regolari. La grammatica libera dal contesto aiuta a definire tutte le possibili stringhe di un linguaggio libero dal contesto.
Conclusione
Un'espressione regolare è un metodo per la corrispondenza dei modelli. È un metodo flessibile per fornire un mezzo flessibile e conciso per far corrispondere le stringhe di testo. Definisce tutte le stringhe nella lingua normale. D'altra parte, la grammatica context free permette di definire tutte le stringhe che appartengono ad un linguaggio context free. La differenza tra l'espressione regolare e la grammatica libera dal contesto è che le espressioni regolari aiutano a descrivere tutte le stringhe di una lingua normale mentre la grammatica libera dal contesto aiuta a definire tutte le possibili stringhe di un linguaggio libero dal contesto.
Riferimento:
1. "Espressioni regolari". Www.tutorialspoint.com, Tutorials Point, 8 gennaio 2018, disponibile qui.
2. "Introduzione alla grammatica libera dal contesto." Www.tutorialspoint.com, Tutorials Point, 8 gennaio 2018, disponibile qui.
Cortesia dell'immagine:
1. "Toolbaricon RegEx" di M0tty - Opera propria (CC BY-SA 4.0) via Commons Wikimedia
