Grammatica regolare e irregolare

Salve a tutti,
qualcuno mi sa spiegare la differenza fra una grammatica regolare e una irregolare?

So che per i linguaggi si usa il Pumping Lemma, ma per la grammatica? Quali particolarità deve avere?

Comments

  • MindFlyerMindFlyer Posts: 436
    Una grammatica è regolare destra se ogni sua produzione è di una delle seguenti forme:
    [tex]A\longrightarrow \varepsilon[/tex]
    [tex]A\longrightarrow a[/tex]
    [tex]A\longrightarrow aB[/tex]
    dove [tex]a[/tex] è terminale e [tex]A[/tex] e [tex]B[/tex] sono non terminali.

    Una grammatica è regolare sinistra se ogni sua produzione è di una delle seguenti forme:
    [tex]A\longrightarrow \varepsilon[/tex]
    [tex]A\longrightarrow a[/tex]
    [tex]A\longrightarrow Ba[/tex]
    dove [tex]a[/tex] è terminale e [tex]A[/tex] e [tex]B[/tex] sono non terminali.

    Una grammatica è irregolare se non è regolare destra e non è regolare sinistra.

    Le grammatiche regolari destre (rispettivamente, sinistre) descrivono tutti e soli i linguaggi regolari. Quindi il Pumping Lemma vale anche per le grammatiche regolari. Il Pumping Lemma esprime una proprietà "semantca" dei linguaggi, non una proprietà "sintattica". Vale a dire che, a prescindere dal formalismo che usi per descrivere un linguaggio regolare, il Pumping Lemma vale nello stesso modo.
  • ManutioManutio Posts: 22
    Ok! Adesso è chiaro, grazie!
  • mz_mz_ Posts: 60
    aggiungerei anche che se G è una grammatica regolare sinistra, allora esiste G' grammatica regolare destra che genera lo stesso linguaggio generato da G.
  • MindFlyerMindFlyer Posts: 436
    Esatto, è quello che intendevo con "Le grammatiche regolari destre (rispettivamente, sinistre) descrivono tutti e soli i linguaggi regolari."
Sign In or Register to comment.