[Automi e Linguaggi formali] Linguaggi formali

[Gervaso90]

Ciao a tutti!
Mi stavo esercitando nella definizione di linguaggi formali "traducendo in prosa " le varie notazioni, sono incappato in un esercizio che non riesco a tradurre. Il linguaggio è descritto in questo modo:

$ L = { w\in{a,b}$*$ | \phi b(w) \wedge \neg \phi a(w)} $

dove il predicato è definito in questo modo:
$\phi x(\epsilon)=true$
$\phix(wy)=\phi(w)$ $ se \ x\ne y)$
$\phix(wy)=\neg\phi(w)$ $ se \ x=y)$

Qualcuno potrebbe spiegarmi cosa chiede questo linguaggio?

Grazie a tutti in anticipo

[apatriarca]

Per prima cosa cerchiamo di capire che cosa rappresenta il predicato in termini più semplici. Sappiamo che se la stringa è vuota il predicato è vero. Per ogni lettera nella stringa \(y\) uguale a \(x\), \(\phi_x\) viene negata. Abbiamo quindi che il numero di negazioni è uguale al numero di caratteri uguali a \(x\) nella stringa e sarà quindi vero se il numero è pari e falso se il numero è dispari. Il tuo linguaggio chiede quindi che ci siano un numero pari di \(b\) e un numero dispari di \(a\).

[Gervaso90]

Ciao! Per prima cosa ti ringrazio per aver risposto , ho seguito il tuo ragionamento, ma non ho ben capito probabilmente come funziona la negazione, prendendo in considerazione una parola come w = abb, come dovrebbe funzionare il linguaggio?

[apatriarca]

\[ \begin{align*}
\phi_b(abb) &= \neg \, \phi_b(ab) = \neg \, \neg \, \phi_b(a) = \phi_b(\epsilon) = \text{true} \\
\phi_a(abb) &= \phi_a(ab) = \phi_a(a) = \neg \, \phi_a(\epsilon) = \text{false}.
\end{align*}
\]

[Gervaso90]

Penso di aver capito, quindi essendo il predicato ϕb vero e ϕa falso, la parola è accettata dal linguaggio. Ti ringrazio vivamente per la spiegazione dettagliata.