Γλώσσα

Δείξτε ότι η γλώσσα

δεν είναι κανονική, με χρήση του Λήμματος Άντλησης.

Ορίζουμε αναδρομικά της συμβολοσειρά W_n με τον παρακάτω τρόπο:W₀₌ε

• W_κ+1=W_κ10^κ+1
• Για παράδειγμα W₁ =10, W₁₂=10100, W₁₂=101001000.

Εφαρμόζοντας την τεχνική των διαχωριζόμενων συμβολοσειρών, δείξτε ότι η γλώσσα

L={Wn | n>0} δεν είναι κανονική.

(Γ)       Δείξτε ότι η γλώσσα  

δεν είναι ανεξάρτητη συμφραζομένων.