Note de curs, clasele 11-12, 2 noiembrie 2012
From Algopedia
Jump to navigationJump to search
Automate finite
- definiție: A = < Q (stări), q0, F (stări de acceptare), Σ (alfabet), δ (tranziții) >
- tranziții ε
- un limbaj este regulat dacă există un automat care îl recunoaște
- procedura de design a unui automat
- exemplu: acceptă șiruri cu nr. impar de 1
- ce am nevoie să memorez despre șirul de până acum?
- exemplu: acceptă șiruri care conțin 001 ca subșir
- tipuri de cerințe
- (1) ce face acest automat
- (2) să se creeze un automat care face X
- operații regulate: ∪ (reuniune), ∘ (concatenare), * (star)
- clasa limbajelor regulate este închisă sub operațiile regulate
- demonstrații pentru uniune, intersecție
- automate finite nedeterministe (NFA)
- tranziții ε
- variante multiple pentru același caracter
- cum funcționează (split)
- echivalență DFA ⇔ NFA (2k stări și tranziții E(δ(r, a)))
- exemple
- refacerea demonstrației pentru închiderea la uniune folosind NFA
- demonstrații cu NFA pentru închiderea la intersecție, star
- limbaje regulate
- exemple: șiruri care conțin exact un 1, șiruri care conțin cel puțin un 1
- echivalență limbaje regulate ⇔ automate finite
- demonstrație într-un singur sens: pentru un limbaj regulat, arătăm cum se construiește NFA-ul.
- lema de pompare
- demonstrație
- exemplu: 0n1n nu este regulat
- exemplu: {w | w conține numere egale de 0 și 1} nu este regulat
- exemplu: { ww | w ∈ {0,1}*} nu este regulat
- exemplu: 1n2 nu este regulat
- exemplu: 0i1j, unde i > j, nu este regulat
Probleme
Am o tonă de probleme, am făcut cam 1/3 la tablă, 1/3 lăsate ca temă, iar 1/3 nu le-am mai dat.
- automat care decide dacă un număr în baza 10 are exact două cifre distincte
- automat care numără cuvintele [a-z]+ și numerele [0-9]+
- automat care decide dacă o secvență este monotonă
- automat care decide dacă un șir se termină în 1
- idem, dar acceptă și șirul vid
- automat care decide dacă un șir se termină într-un număr par de 0
- automat care decide dacă un șir începe și se termină cu același simbol
- automat care decide dacă un număr zecimal se divide cu 3
- automat care decide dacă un șir conține un număr impar de 1
- automat care decide dacă un șir conține 001 ca subșir
- NFA și DFA care decid dacă un șir conține 1 pe antepenultima poziție
- NFA și DFA care decid dacă un șir conține 11 sau 101 ca subșir
- NFA și DFA care decid dacă un subșir conține k simboluri, unde k este multiplu de 2 sau de 3
- etc (încă vreo 10)
