PDA

View Full Version : [C] Se dovessi fare la potenza di linguaggi come sarebbe l'algoritmo ?

misterx
14-07-2010, 08:41
ciao,
ad esempio ho il linguaggio così definito: L={a,b}; come sarebbe l'algoritmo che mi calcola L^2, L^3, L^n ?

Una fila di cicli for/while mi sembra una strada improponibile o no ?


grazie

ciao
WarDuck
14-07-2010, 09:19
L = {a, b} significa che solo le due parole 'a' e 'b' sono nel linguaggio.

L^2 dovrebbe essere L concatenato ad L, quindi saranno le parole 'aa', 'ab', 'ba', 'bb'.

In pratica sono tutte le combinazioni di a e di b lunghe n.
misterx
14-07-2010, 09:28
L = {a, b} significa che solo le due parole 'a' e 'b' sono nel linguaggio.

L^2 dovrebbe essere L concatenato ad L, quindi saranno le parole 'aa', 'ab', 'ba', 'bb'.

In pratica sono tutte le combinazioni di a e di b lunghe n.

ciao,
esatto, ma credo che non valga la proprietà commutativa!

Che algoritmi si usano solitamente, quelli risocrsivi forse ?
WarDuck
14-07-2010, 11:06
ciao,
esatto, ma credo che non valga la proprietà commutativa!


In realtà ho sbagliato volevo dire disposizioni, dato che l'ordine è rilevante.

Comunque ovviamente non vale la proprietà commutativa:

Se tu avessi L1 = {a, b} ed L2 = {c, d} sarebbe più evidente.

L1.L2 = {ac, ad, bc, bd}
L2.L1 = {ca, cb, da, db}

Quindi varrebbe che L2.L1 = L1.L2 reverse.


Che algoritmi si usano solitamente, quelli risocrsivi forse ?

Si, credo siano più appropriati per le disposizioni.
tuccio`
14-07-2010, 13:17
ciao,
esatto, ma credo che non valga la proprietà commutativa!

Che algoritmi si usano solitamente, quelli risocrsivi forse ?backtracking