Linguaggio delle stringhe equilibrate
Ciao, amici! Sia $L$ il linguaggio costituito dalle stringhe non nulle equilibrate sull'alfabeto \(\{0,1\}\), cioè le stringhe in cui occorre lo stesso numero di $0$ e $1$.
Definito per induzione il linguaggio \(L'\) come
1. \(0,1\in L'\).
2. \(\alpha\in L'\Rightarrow 0\alpha 1,1\alpha 0\in L'\).
3. \(\alpha,\beta\in L'\Rightarrow \alpha\beta\in L'\).
Leggo sulla Logica matematica di Vincenzo Manca che "è evidente che \(L'\subseteq L\)", ma c'è qualcosa che mi sfugge.
Dato che per esempio \(1\in L'\), la proprietà 2 non dovrebbe implicare che \(01 1,110\in L'\), anche se, ovviamente, \(011\notin L'\) e \(110\notin L'\)?
$\infty$ grazie per ogni chiarimento!!!
Definito per induzione il linguaggio \(L'\) come
1. \(0,1\in L'\).
2. \(\alpha\in L'\Rightarrow 0\alpha 1,1\alpha 0\in L'\).
3. \(\alpha,\beta\in L'\Rightarrow \alpha\beta\in L'\).
Leggo sulla Logica matematica di Vincenzo Manca che "è evidente che \(L'\subseteq L\)", ma c'è qualcosa che mi sfugge.
Dato che per esempio \(1\in L'\), la proprietà 2 non dovrebbe implicare che \(01 1,110\in L'\), anche se, ovviamente, \(011\notin L'\) e \(110\notin L'\)?
$\infty$ grazie per ogni chiarimento!!!
Risposte
Ciao Davide 
Secondo me c'è un errore nel punto $1$ della definizione per induzione. Se è vero che $L' \subseteq L$ non può essere che $0, 1 \in L'$ in quanto sia $0$ che $1$ non sono evidentemente stringhe equilibrate. Se infatti il punto $1$ lo si cambia con $01, 10 \in L'$ allora il tutto torna. Questa definizione induttiva del linguaggio la si può riscrivere tranquillamente mediante una grammatica (che secondo me è anche più chiara).
Solo per pura curiosità mi stavo chiedendo cos'ha "in meno" $L'$ rispetto ad $L$ ma non sono riuscito ancora a trovare una differenza tra questi due linguaggi, ergo una proprietà che hanno le stringhe equilibrate di $L$ che $L'$ invece non ha.
Secondo me c'è un errore nel punto $1$ della definizione per induzione. Se è vero che $L' \subseteq L$ non può essere che $0, 1 \in L'$ in quanto sia $0$ che $1$ non sono evidentemente stringhe equilibrate. Se infatti il punto $1$ lo si cambia con $01, 10 \in L'$ allora il tutto torna. Questa definizione induttiva del linguaggio la si può riscrivere tranquillamente mediante una grammatica (che secondo me è anche più chiara).
Solo per pura curiosità mi stavo chiedendo cos'ha "in meno" $L'$ rispetto ad $L$ ma non sono riuscito ancora a trovare una differenza tra questi due linguaggi, ergo una proprietà che hanno le stringhe equilibrate di $L$ che $L'$ invece non ha.
Ah, ecco...
Per quanto riguardo che cos'abbia "in meno" \(L'\), in effetti, il testo dimostra (p. 39) che \(L\subseteq L'\) e quindi \(L'=L\).
Tuttavia, dato che, con il punto 1 modificato come da te proposto, chiaramente \(0,1\in L\setminus L'\) e perciò non vale tale uguaglianza. Mah...
$\infty$ grazie!!!
Per quanto riguardo che cos'abbia "in meno" \(L'\), in effetti, il testo dimostra (p. 39) che \(L\subseteq L'\) e quindi \(L'=L\).
Tuttavia, dato che, con il punto 1 modificato come da te proposto, chiaramente \(0,1\in L\setminus L'\) e perciò non vale tale uguaglianza. Mah...
$\infty$ grazie!!!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo