Ce sunt limbajele formale?
Un limbaj formal e o mulțime de șiruri de caractere peste un alfabet finit. Teoria limbajelor formale clasifică aceste limbaje după cât de „puternic" e mecanismul necesar să le recunoști.
Ierarhia Chomsky
Noam Chomsky a clasificat limbajele în 4 niveluri, de la cele mai simple la cele mai expresive:
| Tip | Nume | Automat | Exemplu | |---|---|---|---| | 3 | Regulat | Automat finit | Regex, cuvinte care conțin "ab" | | 2 | Context-free | Automat pushdown | Paranteze corect închise, HTML | | 1 | Context-dependent | Automat liniar mărginit | aⁿbⁿcⁿ | | 0 | Recursiv enumerabil | Mașină Turing | Orice limbaj computabil |
Tipul 3 — Limbaje regulate
Automate finite
Un automat finit (DFA/NFA) are o mulțime finită de stări și tranziții între ele bazate pe simbolul curent.
Exemplu — automat care recunoaște șiruri cu "ab":
Stări: q0 (start), q1 (am văzut 'a'), q2 (acceptare, am văzut "ab")
Tranziții:
q0 --a--> q1
q0 --b--> q0
q1 --b--> q2
q1 --a--> q1
q2 --a,b--> q2
DFA (determinist): o singură tranziție per simbol per stare. NFA (nedeterminist): multiple tranziții, sau ε-tranziții.
Teoremă: Orice NFA poate fi convertit într-un DFA (subset construction). Dimensiunea DFA-ului poate fi exponențial mai mare decât NFA-ul.
Expresii regulate (Regex)
Regex-urile sunt echivalente cu automat finite. Orice expresie regulată poate fi transformată într-un NFA (algoritmul Thompson) și apoi într-un DFA.
Operații de bază:
- Concatenare: "ab" — a urmat de b
- Reuniune: a|b — a sau b
- Steluța Kleene: a* — zero sau mai multe a-uri
Limitare fundamentală: Regex-urile nu pot număra. Nu poți scrie un regex care verifică dacă parantezele sunt corect închise — ai nevoie de un automat pushdown.
Tipul 2 — Limbaje context-free
Automate pushdown
Un automat pushdown (PDA) e un automat finit + o stivă. Stiva îi dă memorie nelimitată, dar cu acces doar în vârf (LIFO).
Exemplu — verificare paranteze:
La fiecare ( → pune pe stivă. La fiecare ) → scoate de pe stivă.
Dacă stiva e goală la final, parantezele sunt corect închise.
Gramatici context-free (CFG)
O gramatică CFG e un sistem de reguli de rescriere:
E → E + T | T
T → T * F | F
F → (E) | id
Acest CFG generează expresii aritmetice simple. Fiecare regulă spune cum poate fi descompus un simbol.
Arbore de derivare: reprezentarea ierarhică a modului în care o propoziție e generată de gramatică.
Aplicație: Toate limbajele de programare sunt definite prin gramatici context-free (sau aproape — vezi analiza semantică).
Tipul 1 — Limbaje context-dependente
Necesită un automat liniar mărginit (LBA) — o mașină Turing a cărei bandă e limitată la o dimensiune proporțională cu inputul.
Exemplu: aⁿbⁿcⁿ — același număr de a, b, c. Un PDA nu poate face asta (ar avea nevoie de două stive).
Tipul 0 — Recursiv enumerabile
Sunt exact limbajele pe care o mașină Turing le poate recunoaște. Nu există un algoritm care să decidă dacă un șir aparține unui astfel de limbaj (problema opririi).
Aplicații practice
| Domeniu | Automat folosit | Exemplu | |---|---|---| | Compilatoare | Analizor lexic (DFA) + analizor sintactic (PDA) | Transformarea codului sursă în AST | | Rețele | Automate finite | Detectarea pachetelor, protocoale de stare | | Procesare text | Regex (NFA/DFA) | Validare email, căutare pattern-uri | | Verificare formală | Automate + logică temporală | Model checking, securitate | | Bioinformatică | Automate finite | Căutarea secvențelor ADN |
Vezi și
- Mașina Turing
- P vs NP
- Lambda Calculus
- Big O