Okej, låt oss utforska vanliga språk med exempel och deras definitioner i formell språktori.
Vad är vanliga språk?
Inom området för formell språkteori är ett regelbundet språk ett språk (en uppsättning strängar över ett givet alfabet) som kan beskrivas av:
* Regelbundna uttryck: Ett mönster som definierar en uppsättning strängar.
* Deterministic Finite Automata (DFA): En maskin som läser inmatning en symbol i taget och övergår mellan tillstånd baserat på ingången. Den accepterar eller avvisar ingången baserat på det slutliga tillståndet.
* icke-deterministiska ändliga automat (NFA): Liknar DFA, men möjliggör flera möjliga övergångar från ett tillstånd för en given insatsymbol (eller till och med övergångar utan att läsa någon inmatning).
* Regelbundna grammatik: En typ av formell grammatik där produktionsregler har en specifik form.
Dessa fyra representationer är likvärdiga. Om du kan definiera ett språk med ett av dessa kan du definiera det med dem alla. Detta är ett grundläggande teorem i formell språktori.
Exempel på vanliga språk
Här är några exempel, tillsammans med hur de kan definieras med hjälp av de metoder som nämns ovan:
1. Språket för alla strängar över {0, 1} som börjar med en '1'.
* Regelbundet uttryck: `1 (0 | 1)*` (eller `1 [01]*`)
* `1` matchar den nödvändiga '1' i början.
* `(0 | 1)` betyder "antingen 0 eller 1".
* `*` betyder "noll eller fler förekomster av föregående grupp."
* dfa:
`` `
0 1
-> Q0 Q1 Q1 (Q0 är starttillståndet)
Q1 Q1 Q1 (Q1 är ett accepterande tillstånd)
`` `
* `Q0` är det ursprungliga tillståndet. Om ingången börjar med '1' övergår den till det accepterande tillståndet `q1 '. Om det börjar med `0`, flyttar det till det icke-accepterande (döda) tillståndet.
* `Q1` är det accepterande tillståndet. När det når detta tillstånd stannar det i det och accepterar ytterligare input.
* nfa: En NFA kan byggas på liknande sätt, men kan ha en alternativ väg från starttillståndet.
* Regelbunden grammatik: (Högerlinjär)
`` `
S -> 1A
A -> 0a | 1A | ε
`` `
* `S` är startsymbolen.
* `A` genererar alla kombinationer av 0s och 1s, inklusive den tomma strängen (ε).
2. Språket för alla strängar över {A, B} som innehåller underlaget "ABA".
* Regelbundet uttryck: `(A | B)*ABA (A | B)*` (eller `[AB]*ABA [AB]*`)
* `(A | B)*` matchar någon sekvens av 'A och' B:er (noll eller mer).
* `ABA` matchar den erforderliga underlaget.
* dfa: Denna DFA kommer att ha stater för att spåra framstegen med att matcha "ABA":
`` `
A B
-> Q0 Q1 Q0
Q1 Q1 Q2
Q2 Q1 Q0
Q3 Q3 Q3 (Q3 är ett accepterande tillstånd)
`` `
* `Q0`:Inledande tillstånd. Representerar att vi inte har sett någon del av "ABA".
* `Q1`:representerar att vi har sett" A ".
* `q2`:representerar att vi har sett" ab ".
* `Q3`:representerar att vi har sett" ABA "(acceptera tillstånd). En gång i `Q3 'håller ytterligare ingångar den i` Q3'.
* nfa: En NFA kan vara enklare att konstruera för detta språk. Det kan "gissa" när "ABA" -underlaget kan börja.
* Regelbunden grammatik:
`` `
S -> som | bs | aa
A -> bb
B -> ac
C -> ac | BC | ε
`` `
3. Språket för alla strängar över {0, 1} med ett jämnt antal 0s.
* Regelbundet uttryck: `1*(01*01*)*`
* `1*`:noll eller flera
*`01*01*`:Detta innebär att strängen ska ha ett jämnt antal 0s, eftersom alla 0 måste följas av `1*01*`, så den är parad.
* dfa:
`` `
0 1
-> Q0 Q1 Q0 (Q0 är början och accepterar tillstånd)
Q1 Q0 Q1 (Q1 är ett icke-accepterande tillstånd)
`` `
* `q0`:till och med antal 0s (starta och acceptera tillstånd).
* `q1`:udda antal 0s.
* nfa: En NFA kan konstrueras, men DFA är ofta den mer enkla representationen.
* Regelbunden grammatik:
`` `
S -> 1S | 0a | ε
A -> 1A | 0S
`` `
4. Språket består av bara strängen "Hello".
* Regelbundet uttryck: "Hej"
* dfa:
`` `
h e l l o
-> Q0 Q1 - - - (Q0 är starttillståndet)
F1 - Q2 - - -
F2 - - F3 - -
F3 - - - Q4 -
F4 - - - - Q5
Q5 - - - - (Q5 är ett accepterande tillstånd)
`` `
* Regelbunden grammatik:
`` `
S -> ha
A -> eb
B -> lc
C -> ld
D -> o
`` `
Exempel på språk som inte är regelbundna
Dessa språk * kan inte * representeras av regelbundna uttryck, DFA, NFA eller regelbundna grammatik. De kräver mer kraftfulla formalismer som kontextfria grammatik eller Turing-maskiner.
1. Strängarnas språk med ett lika antal A:er och 'B: {ε, AB, BA, AABB, ABAB, BABA, BBAA, ...}
2. Språket för palindromer (strängar som läser samma framåt och bakåt): {ε, A, B, AA, BB, ABA, BAB, ABBA, ...}
3. språket {a
n
b
n
| n> =0} :Strängar med `n` 'A följer av' n '' B:er (t.ex. ε, AB, AABB, AAABBB, ...). Detta är ett klassiskt exempel som ofta används för att visa begränsningarna för vanliga språk.
4. Språket {a
n
B
m
c
n
| n, m> =0} :Strängar med "n" a, följt av "m" b's och "n" c. Detta är icke-regelbundet.
Varför är dessa språk inte regelbundna?
Den viktigaste begränsningen av vanliga språk är deras oförmåga att "räkna" eller "komma ihåg" en godtycklig mängd information. En DFA, NFA eller regelbundet uttryck har ett ändligt antal tillstånd eller symboler. Att känna igen språk som {a
n
b
n
}, du skulle behöva hålla reda på antalet A:er som du har sett för att se till att det finns samma antal "B:er. En ändlig automat har inte minneskapaciteten att göra detta för godtyckligt stora `n`. Denna intuition formaliseras av *pumpande lemma för vanliga språk *, ett kraftfullt verktyg för att bevisa att ett språk är *inte *regelbundet.
Sammanfattningsvis
Regelbundna språk är en grundläggande klass av språk i formell språkteori. De är enkla att definiera och implementera, vilket gör dem användbara för många praktiska tillämpningar (t.ex. lexikal analys i kompilatorer, mönstermatchning i textredaktörer, nätverksrutning). De har emellertid begränsningar, och mer komplexa språk kräver mer kraftfulla formalismer.
