Shared Flashcard Set

Details

AAG - 1
1
9
Computer Science
Undergraduate 1
06/19/2017

Additional Computer Science Flashcards

 


 

Cards

Term
Co je to abeceda?
Definition
konečná množina symbolů (značíme Σ nebo T)
Term
Co je to řetězec?
Definition
konečná posloupnost symbolů abecedy
Term
značení množiny všech řetězců nad Σ
Definition
Σ*
Term
množina všech neprázdných řetězců nad Σ
Definition
Σ+
Term
Operace zřetězení
Definition
x,y∈Σ,připojením řetězce y za řetězec x vznikne řetězec x.y
Term
Délka řetězce
Definition
|x| >= 0 || |x| = 0 <=> x = ε
Term
Reverze řetězce
Definition
x = a1a2...an
xR=an...a2a1
Term

Formální jazyk L nad Σ

Definition
L ⊆ Σ*    (množina řetězců)
Term
Operace s formálním jazykem L nad Σ
Definition
  • množinové: ∪, ∩, \
  • komplement jazyka L1:L1\L1
  • součin jazyků L=L1.L2={xy:x∈L1,y∈L2}(L je definován nad abecedou Σ=Σ1∪Σ2)
  • n-tá mocnina jazyka L:Ln=L.Ln−1,L0={ε}.
  • iterace (Kleene star) L* jazyka L: L*=Un=0Ln
Supporting users have an ad free experience!