TIN 14. Regulární množiny, regulární výrazy a rovnice nad regulárními výrazy

Card Set Information

Author:
hrbi
ID:
222595
Filename:
TIN 14. Regulární množiny, regulární výrazy a rovnice nad regulárními výrazy
Updated:
2013-06-05 17:41:54
Tags:
tin
Folders:

Description:
mssz 2013
Show Answers:

Home > Flashcards > Print Preview

The flashcards below were created by user hrbi on FreezingBlue Flashcards. What would you like to do?


  1. Regulární množina
    • RM nad Σ:
    • 1. Ø je RM
    • 2. {ε} je RM
    • 3. {a} je RM pro všechna a ∈ Σ
    • 4. P, Q jsou RM, pak P∪Q, P·Q, P* jsou RM
  2. Regulární výraz
    • RV nad Σ:
    • 1. Ø je RV ozn. RM Ø
    • 2. ε je RV ozn. RM {ε}
    • 3. a je RV ozn. RM {a} pro všechna a ∈ Σ
    • 4. p, q jsou RV, pak (p+q), (pq), (p*) jsou RV ozn. RM P∪Q, P·Q, P*
    • konvence:
    • 1. p+ značí pp*
    • 2. priority operátorů: *, +, ·, +
  3. Kleeneho algebra
    • (A, +, ·, 0, 1, *) splňující 13 axiomů...
    • příklad: (2Σ*, ∪, ·, Ø, {ε}, *)
  4. Rovnice nad RV
    • rovnice, jejímiž složkami jsou koeficienty a neznámé, které reprezentují RV
    • X = pX + q, řešení je X = p*q
  5. Převod RM na lineární gramatiku
    • 1. Ø ... ({S}, Σ, Ø, S)
    • 2. {ε} ... ({S}, Σ, {S → ε}, S)
    • 3. {a} ... ({S}, Σ, {S → a}, S)
    • 4. P∪Q ... sjednotím neterminály, terminály i pravidla, přidám pravidlo S → S1 | S2
    • 5. P·Q ... pravidla z P1 tvaru A → xB zkopíruju, pravidla A → x změním na A → xS2, pak zkopíruju všechna pravidla z P2
    • 6. P* ... pravidla z P1 tvaru A → xB zkopíruju, pravidla A → x změním na A → xS, přidám pravidlo S → ε | S1

What would you like to do?

Home > Flashcards > Print Preview