18.04.2018 - Operationen auf Sprachen, Potenz einer Sprache, Sprachen beschreiben

  • $\Sigma ...$ - Alphabet

    $\Sigma^* ...$ - Menge der Wörter

    $|w| ...$ - Länge eines Wortes

    $L \subseteq \Sigma^* ...$ - Sprache


    Entscheidungsproblem:

    Geg.: $w \in \Sigma^* , L \subseteq \Sigma^*$

    Frage: $w \in L$?


    Operationen auf Sprachen

    Seien $L_1, L_2 \subseteq \Sigma^*$ beliebige Sprachen

    • $L_1 \cup L_2, L_1 \cap L_2. L_1 \backslash L_2$ sind ebenfalls Sprachen
    • $\bar{L_1} = \Sigma^* \backslash L_1$ ist die Komplementärsprache

    Definition: Konkatenation

    Seien $w_1 = \sigma_1 ... \sigma_m \in \Sigma^*$ und $w_2 = \tau_1 ... \tau_2 \in \Sigma^*$

    $w_1 \circ w_2 = \sigma_1 ... \sigma_m\tau_1 ... \tau_n$


    Bsp.:


    $w_1 = haus ; w_2 = boot$

    $w_1 \circ w_2 = hausboot; w_2 \circ w_1 = boothaus$


    $(\circ)$ ist nicht kommutativ

    $(\circ)$ ist assoziativ: $w_1 \circ (w_2 \circ w_3) \equiv (w_1 \circ w_2) \circ w_3$

    $(\circ)$ besitzt ein neutrales Element, $\epsilon$ ist das neutrale Element: $w = \epsilon \circ w = w \circ \epsilon \rightarrow Monoid$


    $(\circ)$ besitzt keine inversen Elemente


    $|w_1 \circ w_2| = |w_1| + |w_2|$