Λέξεις από άλλες λέξεις 2

αρψ2400 · #1

Αν

και

μπορείτε να μετατρέψετε τη συμβολοσειρά ab^na

στη συμβολοσειρά ba^nb

για $n\geq 4$ ? (οι αντικαταστάσεις ab=baa

και

είναι προφανώς αμφίδρομες.Για n=1,2,3

η μετάβαση είναι εφικτή.Θα μειώσω κατά ένα τον αριθμό των a,b

στη δημόσια συζήτηση ''Λέξεις από άλλες λέξεις'' για να έχουμε την περίπτωση n =4

).

αρψ2400 · #2

Με επαγωγή.Για n=4

, ισχύει https://mathematica.gr/forum/viewtopic ... 44&t=78018 . Έστω ότι ισχύει για

θα δέιξουμε ότι ισχύει για n+1

.

$\displaystyle ab^{n+1} a = (ab)b^n a =$
$\displaystyle ba(ab^n a) = baba^{n} b =$
$\displaystyle ba(baa)a^{n-2}b = (baa)ba^{n-2}b =$
$\displaystyle abba^{n-2}b = a(bbaa)a^{n-4}b =$
$\displaystyle a(ab)aa^{n-4}b = abaaaa^{n-4}b =$
$\displaystyle (ab)a^{n-1}b = baaa^{n-1}b = ba^{n+1}b$

Λέξεις από άλλες λέξεις 2

Λέξεις από άλλες λέξεις 2

Re: Λέξεις από άλλες λέξεις 2

Μέλη σε σύνδεση