Kontextfreie Grammatiken - Theoretische Informatik - Alphabeten

Question

Sei A ein beliebiges Alphabet.
Geben Sie ein Schema an, welches abhängig von A genau die Grammatik G A mit
L( Ga ) = {w ∈ A∗ | w ist ein Palindrom} erzeugt. Geben Sie hierzu Na , Ta , Pa , sowie
das Startsymbol der Grammatik (ggf. abhängig von A) a.

Answer 1

Produktionsregeln sind

• \(S\to aSa\) für jedes \(a\in A\)
• \(S\to a\) für jedes \(a\in A\)
  
• \(S\to \varepsilon\)