Please enable JavaScript.

Coggle requires JavaScript to display documents.

Grammatiche CFG - Coggle Diagram

- - - - Da u posso arrivare a v con una seq. di sostituzioni
- - - - Si usa quando i linguaggi complessi è unione di due linguaggi più semplici
        
        Si costruiscono
        
        Due grammatiche separate
        
        Una per il primo linguaggio
        
        Una per il secondo linguaggio
        
        Si crea una nuova variabile iniziale questa può generare una grammatica
    - - Se il linguaggio è regolare
        
        Allora ha un DFA
        
        Trasformare in una CFG
      - Ogni stato del DFA diventa una variabile della grammatica
      - Ogni transizione da q_i a q_j leggendo a, diventa R_i --> aR_j
      - Ogni stato finale diventa anche una regola verso ε
      - Ogni stato iniziale diventa simbolo iniziale della grammatica
    - - Si utilizzano quando bisogna bilanciare due parti della stringa
    - - Si utilizza quando una scrittura può comparire dentro se stessa
        
        Contiene una parte che ha la stessa forma della parte intera
        
        Regola: S --> (S) | ε