Det finns flera sätt att visa att ett språk är kontextfritt. Här är en uppdelning av vanliga tekniker och överväganden:
1. Ge en kontextfri grammatik (CFG):
* Den mest direkta och ofta använda metoden. Om du kan designa en CFG som genererar * exakt * strängarna på språket har du bevisat att det är kontextfritt.
* CFG Definition: En CFG består av:
* * Icke-terminaler (variabler):* Representerat av versaler (t.ex. `s`,` a`, `b`).
* * Terminaler:* Alfabetssymbolerna för språket (t.ex. `A`,` B`, `0`,` 1`).
* * Startsymbol:* En utmärkta icke-terminal (vanligtvis `s`).
* * Produktionsregler:* Reglerna för formen `icke -terminal -> sträng av terminaler och/eller icke -terminaler` (t.ex.` s -> asb | ε`).
* Hur man använder: Visa att varje sträng på språket kan härledas från startsymbolen med hjälp av produktionsreglerna. Visa också att grammatiken * inte * genererar några strängar som är * inte * på språket.
* Exempel:
* Språk:l ={a
n
b
n
| n ≥ 0} (strängar med lika många "A och" B:er, i den ordningen)
* CFG:
* `S -> ASB | ε` (Where ε representerar den tomma strängen)
* Förklaring:
* `S` genererar kärnmönstret` ASB`.
* Genom att rekursivt tillämpa regeln `s -> asb` kan du skapa valfritt antal` a`s och `b`s, vilket säkerställer att de är balanserade.
* "S -> ε" -regeln låter dig avsluta rekursionen och producera den tomma strängen (som också finns på språket när n =0).
2. Ge en pushdown -automat (PDA):
* motsvarande CFGS: Alla språk som accepteras av en PDA är kontextfritt och vice versa. Denna ekvivalens är ett grundläggande resultat i automatteori.
* PDA -definition: En PDA är en ändlig automat med en stack. Den kan läsa inmatningssymboler, ändra sitt tillstånd och trycka eller popsymboler från stacken.
* Hur man använder: Designa en PDA som accepterar exakt strängarna på språket. Ofta används stacken för att hålla reda på "oöverträffade" symboler.
* Exempel (för samma språk l ={a
n
b
n
| n ≥ 0}):
* PDA läser 'A och skjuter dem på bunten.
* När det möter en 'b', dyker det upp en 'a' från stacken.
* PDA accepterar om den har läst alla ingångar och stacken är tom.
* Viktigt: Ange hur PDA -övergångarna mellan tillstånd baserat på inmatningssymboler och stapelinnehåll.
3. Använd stängningsegenskaper:
* Kontextfria språk stängs under vissa operationer. Detta innebär att om du vet att vissa språk är kontextfria kan du kombinera dem med hjälp av dessa operationer för att skapa nya kontextfria språk.
* Stängningsegenskaper:
* Union: Om L1 och L2 är kontextfria är L1 ∪ L2 kontextfri.
* Concatenation: Om L1 och L2 är kontextfria är L1L2 kontextfri.
* Kleene Star ( *): Om L är kontextfri är l* kontextfri.
* homomorfism: Om L är kontextfri och `H` är en homomorfism (en funktion som kartlägger symboler till strängar), är` h (l) 'kontextfri.
* omvänd homomorfism: Om L är kontextfri och `H` är en homomorfism,` H
-1
(L) `är kontextfri. (Inverse homomorfism tar en sträng som input och returnerar uppsättningen av strängar som, när homomorfismen tillämpas, ger dig inmatningssträngen).
* Hur man använder: Nedbrytning av målspråket till enklare språk som du * redan vet * är kontextfria och kombinerar dem sedan med stängningsegenskaper.
* Exempel:
* Visa att l ={a
n
b
n
c
m
d
m
| n, m ≥ 0} är kontextfri.
* L1 ={a
n
b
n
| n ≥ 0} är kontextfri (vi vet redan detta).
* L2 ={c
m
d
m
| M ≥ 0} är kontextfri (liknande L1).
* L =L1L2 (sammankopplingen av L1 och L2).
* Eftersom L1 och L2 är kontextfria och kontextfria språk stängs under sammankoppling, är L kontextfri.
4. Pumpande lemma för kontextfria språk (för att bevisa ett språk är * inte * kontextfritt):
* Viktigt: Pumpande lemma är van vid * motbevisa * att ett språk är kontextfritt. Det kan inte användas för att bevisa att ett språk * är * kontextfritt.
* Hur det fungerar: Pumpande lemma säger att för alla kontextfria språk l finns det en pumplängd 'p' så att alla strängar 'i L med längd åtminstone' p 'kan delas upp i fem delar, s =uvxyz, var::
1. | Vxy | ≤ P (den mellersta delen är inte för lång)
2. | Vy | ≥ 1 (den del som ska upprepas är inte tom)
3. För allt jag ≥ 0, uv
i
xy
i
Z är i L (du kan upprepa 'v' och 'y' valfritt antal gånger, och den resulterande strängen finns fortfarande på språket).
* Bevis i motsägelse:
1. Antag att språket är kontextfritt.
2. Antag att det finns en pumplängd 'p' som beskrivs i lemma.
3. Välj en sträng 's' på det språk som är längre än 'p'. Valet av 's' är avgörande. Det borde ha egenskaper som gör pumpning problematisk.
4. Tänk på * alla möjliga * sätt att dela 's' i 'uvxyz' som tillfredsställer förhållandena 1 och 2 i pumpande lemma.
5. För * varje * möjlig uppdelning, visa att det finns en 'i' (vanligtvis i =0 eller i =2) så att UV
i
xy
i
Z är * inte * på språket.
6. Detta strider mot pumpande lemma, så det första antagandet att språket är kontextfritt måste vara falskt.
Vilken metod som ska användas:
* grammatik/PDA -konstruktion: Det vanligaste och ofta enklaste sättet att visa ett språk * är * kontextfritt. Välj vilket (CFG eller PDA) är lättare att konstruera för det specifika språket. Om språket verkar involvera kapslade eller rekursiva strukturer är en grammatik ofta en bra utgångspunkt. Om språket lämpar sig för ett stackliknande beteende, överväg att använda en PDA.
* Stängningsegenskaper: Användbart när språket kan uttryckas som en kombination av enklare, redan kända kontextfria språk.
* Pumping Lemma: Exklusivt för att visa ett språk är * inte * kontextfritt.
Viktiga överväganden:
* Regelbundna språk är kontextfria: Varje regelbundet språk är också kontextfritt. Om du kan visa att ett språk är regelbundet (genom att tillhandahålla en DFA, NFA eller regelbundet uttryck) har du också visat att det är kontextfritt. Men ofta kommer en CFG eller PDA att vara det mer enkla tillvägagångssättet om språket är * uppenbarligen * kontextfritt.
* icke-deterministiska PDA: I allmänhet är PDA:er icke-deterministiska. Deterministiska PDA:er (DPDA) är mindre kraftfulla; De accepterar en korrekt delmängd av de kontextfria språken (kallas de deterministiska kontextfria språken). Om du inte uttryckligen anges kan du anta att du har att göra med allmänna (icke-deterministiska) kontextfria språk.
* noggrann definition: Oavsett om du utformar en grammatik eller en PDA, var mycket exakt i dina definitioner. Undvik tvetydighet och förklara tydligt hur din konstruktion fungerar.
* Exempel: Arbeta igenom många exempel för att få en god förståelse för dessa tekniker. Övning är nyckeln!
Sammanfattningsvis, för att * bevisa * ett språk är kontextfritt, bygga en CFG eller PDA för det eller visa dess kontextfrekvens genom stängningsegenskaper. Använd pumpens lemma för kontextfria språk för att visa att ett språk är * inte * kontextfritt. Lycka till!
