Kontekstfritt språk

Et kontekstfritt språk er språket generert av en kontekstfri grammatikk.
Innenfor programmeringsspråk har kontekstfrie språk ei rekke anvendelser. De fleste aritmetiske uttrykk er generert av kontekstfrie grammatikker. Innenfor kompilatorteknikk er teorien om kontekstfrie språk også viktig.
I Chomskyhierarkiet er kontekstfrie språk omtalt som de som genererer en type 2 grammatikk.


== Eksempel ==
Et eksempel er følgende språk 
  
    
      
        L
        =
        {
        
          a
          
            n
          
        
        
          b
          
            n
          
        
        :
        n
        ≥
        1
        }
      
    
    {\displaystyle L=\{a^{n}b^{n}:n\geq 1\}}
  . Dette er generert av grammatikken 
  
    
      
        S
        →
        a
        S
        b
         
        
          |
        
         
        a
        b
      
    
    {\displaystyle S\to aSb~|~ab}
  . Den er akseptert av følgende pushdownautomat 
  
    
      
        M
        =
        (
        {
        
          q
          
            0
          
        
        ,
        
          q
          
            1
          
        
        ,
        
          q
          
            f
          
        
        }
        ,
        {
        a
        ,
        b
        }
        ,
        {
        a
        ,
        z
        }
        ,
        δ
        ,
        
          q
          
            0
          
        
        ,
        z
        ,
        {
        
          q
          
            f
          
        
        }
        )
      
    
    {\displaystyle M=(\{q_{0},q_{1},q_{f}\},\{a,b\},\{a,z\},\delta ,q_{0},z,\{q_{f}\})}
   hvor 
  
    
      
        δ
      
    
    {\displaystyle \delta }
   er definert som følgende

  
    
      
        δ
        (
        
          q
          
            0
          
        
        ,
        a
        ,
        z
        )
        =
        (
        
          q
          
            0
          
        
        ,
        a
        z
        )
      
    
    {\displaystyle \delta (q_{0},a,z)=(q_{0},az)}
  

  
    
      
        δ
        (
        
          q
          
            0
          
        
        ,
        a
        ,
        a
        )
        =
        (
        
          q
          
            0
          
        
        ,
        a
        a
        )
      
    
    {\displaystyle \delta (q_{0},a,a)=(q_{0},aa)}
  

  
    
      
        δ
        (
        
          q
          
            0
          
        
        ,
        b
        ,
        a
        )
        =
        (
        
          q
          
            1
          
        
        ,
        ε
        )
      
    
    {\displaystyle \delta (q_{0},b,a)=(q_{1},\varepsilon )}
  

  
    
      
        δ
        (
        
          q
          
            1
          
        
        ,
        b
        ,
        a
        )
        =
        (
        
          q
          
            1
          
        
        ,
        ε
        )
      
    
    {\displaystyle \delta (q_{1},b,a)=(q_{1},\varepsilon )}
  


== Egenskaper ==
Kontekstfrie språk er lukket under følgende operasjoner. Det vil altså si at for to kontekstfrie språk L og P, så vil resultatet av operasjonen fortsatt være et kontekstfritt språk.

Kleenestjerna av L
Reverseringa av L
Unionen av L og P
Konkateneringa av L og P
Bildet under en homomorfisme (eller en invers homomorfisme)
Det sirkulære skiftet av språketKontekstfrie språk er altså ikke lukket under komplement og snitt.


== Se også ==
Chomsky normalform
Pushdownautomat
Pumpelemmaet for kontekstfrie språk


== Litteratur ==
Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
Kozen, D.C. (1997), Automata and Computability, Springer.