Grammatiche regolari e libere dal contesto

StackOverflow https://stackoverflow.com/questions/559763

Domanda

Sto studiando per mio linguaggi informatici test, e c'è un'idea che non riesco a capire.

io ho capito quello grammatiche regolari sono più semplici e non possono contenere ambiguità, ma non possono svolgere molte attività richieste per i linguaggi di programmazione.L'ho capito anche io grammatiche libere dal contesto consentire l'ambiguità, ma consentire alcune cose necessarie per i linguaggi di programmazione (come i palindromi).

Ciò con cui ho problemi è capire come posso ricavare tutto quanto sopra sapendolo non terminali della grammatica regolare può mappare a un terminale o a un non terminale seguito da un terminale o che un non terminale libero dal contesto si mappa a qualsiasi combinazione di terminali e non terminali.

Qualcuno può aiutarmi a mettere insieme tutto questo?

È stato utile?

Soluzione

grammatica regolare è di destra o di sinistra lineari, mentre nell'ambito della grammatica libera è in pratica qualsiasi combinazione di terminali e non terminali. Da qui si può vedere che la grammatica regolare è un sottoinsieme della grammatica context-free.

Quindi, per un palindromo per esempio, è di forma, 

S->ABA
A->something
B->something

Si può chiaramente vedere che palindromi non possono essere espressi in grammatica regolare in quanto ha bisogno di essere a destra oa sinistra lineari e come tale non può avere un non terminale su entrambi i lati.

Poiché grammatiche regolari sono non ambigua, c'è solo una regola di produzione per un dato non terminale, mentre ci possono essere più di uno nel caso di una grammatica libera dal contesto.

Altri suggerimenti

Credo che ciò che si vuole pensare sono i vari lemmi di pompaggio. Un linguaggio regolare può essere riconosciuto da un automa a stati finiti. Un linguaggio context-free richiede uno stack, e un linguaggio sensibile al contesto richiede due pile (il che equivale a dire che richiede una macchina di Turing completo.)

Quindi, se si pensa alle href="http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages" pumping lemma per i linguaggi regolari , quello che dice, in sostanza, , è che ogni linguaggio regolare può essere suddiviso in tre parti, x , y e z , in cui tutte le istanze del linguaggio sono in xy * z (dove * è Kleene ripetizione, cioè 0 o più copie di y .) Hai sostanzialmente una "non terminale" che può essere espansa.

Ora, che dire di linguaggi context-free? C'è un pumping lemma per i linguaggi liberi dal contesto che rompe le corde nella lingua in cinque parti, uvxyz , e dove tutte le istanze del linguaggio sono in uv i xy i z , per i ≥ 0. Ora, si ha due "nonterminals" che possono essere replicati, o pompati, finchè avete lo stesso numero .

La differenza tra grammatica normale e grammatica libera dal contesto:(N, Σ, P, S) :terminali, non terminali, produzioni, stato iniziale Simboli terminali

● simboli elementari della lingua definiti da una grammatica formale

● abc

Simboli non terminali (o variabili sintattiche)

● sostituiti da gruppi di simboli terminali secondo le regole di produzione

●ABC

grammatica regolare:Grammatica destra o sinistra regolare grammatica regolare destra, tutte le regole obbediscono alle forme

  1. B → a dove B è un non terminale in N e a è un terminale in Σ
  2. B → aC dove B e C sono in N e a è in Σ
  3. B → ε dove B è in N e ε denota la stringa vuota, cioèla stringa di lunghezza 0

lasciata la grammatica regolare, tutte le regole obbediscono alle forme

  1. A → a dove A è un non terminale in N e a è un terminale in Σ
  2. A → Ba dove A e B sono in N e a è in Σ
  3. A → ε dove A è in N e ε è la stringa vuota

grammatica libera dal contesto (CFG)

○ grammatica formale in cui ogni regola di produzione è della forma V → w

○ V è un singolo simbolo non terminale

○ w è una stringa di terminali e/o non terminali (w può essere vuoto)

espressioni regolari

  • Criteri di analisi lessicale
  • rappresentano linguaggi regolari

Context libero Grammatiche

  • Criteri di analisi
  • rappresentano costrutti del linguaggio

entrare descrizione dell'immagine qui

grammatica regolare: - grammatica contenente produzione come segue è RG: 

V->TV or VT
V->T

dove V = variabile e T = terminale

RG può essere lasciato lineare di grammatica o di destra Liner grammatica, ma non grammatica lineare Medio.

Come sappiamo tutti RG sono Lineare grammatica, ma solo Sinistra o Destra lineare lineare grammatica sono RG.

Una grammatica regolare può essere ambiguo. 

S->aA|aB
A->a
B->a

Grammatica Ambiguo: -. per una stringa x loro esiste più di un LMD o più di RMD o più di un albero sintattico o One LMD e One RMD ma entrambi produrre diversi albero di analisi 

                S                   S

              /   \               /   \
             a     A             a     B
                    \                   \
                     a                   a

Questa grammatica è ambigua Grammatica perché due albero sintattico.

CFG: - Una grammatica detto di essere CFG se la sua produzione è in forma: 

   V->@   where @ belongs to (V+T)*

DCFL: - come sappiamo tutti DCFL sono LL (1) Grammatica e tutto LL (1) è LR (1) quindi non è mai ambigua. così DCFG è mai stato ambiguo.

Sappiamo anche tutti RL sono DCFL così RL mai essere ambiguo. Si noti che RG può essere ambigua, ma non RL.

CFL:. CFL può o non ambigue

Nota. RL mai essere intrinsecamente ambiguo

Una grammatica è libera dal contesto se tutte le regole di produzione hanno la forma: A (cioè, il lato sinistro di una regola può essere solo una singola variabile, il lato destro è libera e può essere qualsiasi sequenza di terminali e variabili) . Possiamo definire una grammatica come un 4-tuple dove V è un insieme finito (variabili), _ è un insieme finito (morsetti), S è la variabile di inizio, e R è un insieme finito di regole, ciascuna delle quali è una mappatura V
grammatica regolare è o lineare a destra oa sinistra, mentre contesto grammatica libera è in pratica qualsiasi combinazione di terminali e non terminali. quindi possiamo dire che la grammatica regolare è un sottoinsieme della grammatica context-free. Dopo queste proprietà si può dire che Context Gratis Lingue set contiene anche linguaggi regolari set

In sostanza la grammatica regolare è un sottoinsieme della grammatica contesto libero, ma non possiamo dire Ogni grammatica Context libero è una grammatica regolare. Principalmente contesto di libero grammatica è ambigua e la grammatica regolare può essere ambigua.

una grammatica regolare è mai ambigua perché è sia lineare, a sinistra oa destra in modo lineare, non vediamo fare due albero decisionale per la grammatica regolare quindi è sempre unambiguous.but othert di grammatica regolare tutti sono può o non può essere regolare

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top