- Clasificare
| Clasificarea Chomsky | Gramatica | Limbajul | Automatul minimal | Forma normala |
| tip 0 | fara restrictie | recursiv enumerabil | MTN | - |
| - | fara restrictie | recursiv | decidor | - |
| tip 1 | dependenta de context | dependent de context | marginit liniar | KURODA |
| tip 2 | independenta de context | independent de context | push down | CHOMSKY, GREIBACH |
| tip 3 | regulara | regular | finit | - |
- Gramatici si limbaje
- O multime finita si nevida, Σ, se numeste alfabet iar elementele se numesc simboluri
- O succesiune de simboluri se numeste secventa si o submultime ordonata a unei secvente se numeste subsecventa
- Numarul de simboluri care formeaza o secventa s se numeste lungimea secventei si se noteaza |s|
- Multimea secventelor peste un alfabet Σ se noteaza Σ*
- (Σ*, +) este monoid unde "+" este concatenarea si elementul neutru este secventa vida ε
- O submultime a lui Σ* se numeste limbaj iar elementele limbajului se numesc cuvinte
- Se numeste gramatica G un cvadruplu (N, Σ, P, s) unde
- N este un alfabet de simboluri neterminale
- Σ este un alfabet de simboluri terminale, N si Σ sunt disjuncte
- P este o multime finita de productii, P⊂ (N∪Σ)*N(N∪Σ)* X (N∪Σ)*
- s este simbolul initial, s∈N
- Pe multimea (N∪Σ)* se definesc relatiile binare
- derivare directa, ⇒
- k derivare, ⇒k
- a ⇒k b daca ∃ c1, c2, ..., ck-1 ∈ (N∪Σ)* ai a ⇒ c1 ⇒ c2 ... ck-1 ⇒ b
- + derivare, ⇒+
- a ⇒+ b daca ∃k ai a ⇒k b
- * derivare, ⇒*
- a ⇒* b daca a ⇒ b sau a ⇒+ b
Limbajul L(G) generat de o gramatica G=(N, Σ, P, s) este {v/ v∈ Σ*, s ⇒* v}Clasificarea Chomsky- Gramaticile de tip 0 nu au nici o restrictie referitoare la forma productiilor
- Gramaticile de tip 1, gramatici dependente de context, au productii de forma αAβ → αγβ unde αβγ ∈ (N∪Σ)* si A ∈ N iar daca productia s → ε ∈ G atunci s nu apare in mebrul drept al nici unei productii (monotone, necontractante)
- Gramaticile de tip 2, gramatici independente de context, au productii de forma A → α unde A ∈ N si α ∈ (N∪Σ)*
- Gramaticile de tip 3, gramatici regulare, au productii de forma A → aB sau A → b unde A, B ∈ N si a, b ∈ Σ
Automate- Automate finite
- Automat finit determinist
- Un cvintuplu AFD=(Q, Σ, δ, q0, F) unde:
- Q este o multime finita nevida; elementele sale se numesc stari
- Σ este un alfabet de intrare
- δ este functia de tranzitie, δ : Q X Σ → Q
- q0 este starea initiala, q0 ∈ Q
- F este multimea starilor finale, F ⊆ Q
Daca δ este surjectiva, AFD este total definit - Automat finit nedeterminist
- Un cvintuplu AFN=(Q, Σ, δ, q0, F) unde:
- Q este o multime finita nevida; elementele sale se numesc stari
- Σ este un alfabet de intrare
- δ este functia de tranzitie, δ : Q X Σ → P(Q)
- q0 este starea initiala, q0 ∈ Q
- F este multimea starilor finale, F ⊆ Q
- Tranzitii
- Multimea configuratiilor unui automat este Q X Σ. Pe multimea configuratiilor se definesc urmatoarele relatii binare
- tranzitia directa, →
- (p, as) → (q, v) ⇔ q = δ(p,a) unde p, q ∈ Q, a ∈ Σ, s ∈ Σ*
- k tranzitia, →k
- (p, s1) → (q, s2) ⇔ de la configuratia (p, s1) se ajunge la configuratia (q, s2) prin k tranzitii directe
- + tranzitia, →+
- (p, s1) →+ (q, s2) ⇔ ∃ k > 0 ai (p, s1) →k (q, s2)
- * tranzitia, →*
- (p, s1) →* (q, s2) ⇔ p=q, s1=s2 sau (p, s1) →+ (q, s2)
- Limbaj acceptat
- Limbajul acceptat de un automat finit AF = (Q, Σ, δ, q0, F) este L(AF) = {s / S ∈ Σ, (p, s) →* (q, ε), q ∈ F }
- Automate echivalente
- Doua AF sunt echivalente daca accepta acelasi limbaj
- ∀ AFN, M1, ∃ AFD, M2 ai L(M1) = L(M2)
- Automate push down
- Un septuplu APD=(Q, Σ, Γ, δ, q0, Z0, F) unde:
- Q este o multime finita nevida; elementele sale se numesc stari
- Σ este un alfabet de intrare
- Γ este alfabetul memoriei stiva
- δ este functia de tranzitie, δ : Q x ( Σ ∪ {ε} ) x Γ → P(Q x Γ*)
- q0 este starea initiala, q0 ∈ Q
- Z0 este simbolul de start al memoriei stiva
- F este multimea starilor finale, F ⊆ Q
- Masini Turing
- Masina Turing determinista
- Un septuplu MTD=(Q, Σ, Γ, δ, q0, B, F) unde:
- Q este o multime finita nevida; elementele sale se numesc stari
- Σ este un alfabet de intrare, Σ ⊂ Γ - {B}
- Γ este alfabetul benzii
- δ este functia de tranzitie, δ : Q x Γ → Q x Γ x {miscareStanga, miscareDreapta}
- q0 este starea initiala, q0 ∈ Q
- B este simbolul spatiu, B ∈ Γ
- F este multimea starilor finale, F ⊆ Q
- Masina Turing nedeterminista
- Un septuplu MTN=(Q, Σ, Γ, δ, q0, B, F) unde:
- Q este o multime finita nevida; elementele sale se numesc stari
- Σ este un alfabet de intrare, Σ ⊂ Γ - {B}
- Γ este alfabetul benzii
- δ este functia de tranzitie, δ : Q x Γ → P( Q x Γ x {miscareStanga, miscareDreapta} )
- q0 este starea initiala, q0 ∈ Q
- B este simbolul spatiu, B ∈ Γ
- F este multimea starilor finale, F ⊆ Q
- Masina Turing probibilista
- MTP este o MTN pentru care selectia intre valorile functiei de tranzitie se face probabilistic
# posted by Sorin Badescu @ 4:11 PM
