Spezifikation formaler Sprachen

man kann eine formale Sprache beschreiben durch:

• algebraisch (Sprach-Operationen)

  Bsp: reguläre Ausdrücke

• Generieren (Grammatik), Bsp: kontextfreie Grammatik,
• Akzeptanz (Automat), Bsp: Kellerautomat,
• logisch (Eigenschaften), $\left\{\vphantom{ w\mid \forall p,r: \left(\begin{array}{ll} & (p<r \wedge w[... ...ghtarrow & \exists q: (p<q \wedge q<r\wedge w[q]=b) \end{array}\right) }\right.$w | ∀p, r : $\left(\vphantom{\begin{array}{ll} & (p<r \wedge w[p]=a \wedge w[r]=c) \\ \Rightarrow & \exists q: (p<q \wedge q<r\wedge w[q]=b) \end{array}}\right.$$\begin{array}{ll} & (p<r \wedge w[p]=a \wedge w[r]=c) \\ \Rightarrow & \exists q: (p<q \wedge q<r\wedge w[q]=b) \end{array}$$\left.\vphantom{\begin{array}{ll} & (p<r \wedge w[p]=a \wedge w[r]=c) \\ \Rightarrow & \exists q: (p<q \wedge q<r\wedge w[q]=b) \end{array}}\right)$$\left.\vphantom{ w\mid \forall p,r: \left(\begin{array}{ll} & (p<r \wedge w[p... ...htarrow & \exists q: (p<q \wedge q<r\wedge w[q]=b) \end{array}\right) }\right\}$