Web Analytics Made Easy - Statcounter

[HOME PAGE] [STORES] [CLASSICISTRANIERI.COM] [FOTO] [YOUTUBE CHANNEL]

Aut??mat finit - Viquip??dia

Aut??mat finit

De Viquip??dia

Esquema l??gic d'un aut??mat finit
Esquema l??gic d'un aut??mat finit

Un aut??mat finit (AF) o m??quina d'estats finits (FSM de l'angl??s Finite State Machine) ??s un model matem??tic d'un sistema compost per estats, transicions i accions. Un estat emmagatzema informaci?? del passat. Una transici?? indica un canvi d'estat i es descriu per la condici?? que ??s necess??ria acomplir per activar la transici??. Una acci?? ??s una descripci?? d'una activitat que es realitza en un moment donat. D'accions n'hi ha de varis tipus:

Acci?? d'entrada
executa l'acci?? quan s'entra a l'estat.
Acci?? de sortida
executa l'acci?? quan s'abandona l'estat.
Acci?? d'Input
executa l'acci?? depenent de l'estat actual i les condicions d'entrada.
Acci?? de Transici??
executa l'acci?? quan succeeix una certa transici??.

Taula de continguts

[edita] Classificaci??

Hi ha dos grups diferenciats: Acceptadors/Reconeixedors i Transductors.

[edita] Acceptadors i reconeixedors

Aquest tipus de maquines donen una sortida binaria, responent si o no si l'entrada s'accepta o no. Alguns dels estats de l'AF es defineixen com finals. Quan tota l'entrada s'ha processat, si l'estat on es troba l'AF ??s un estat final, l'entrada s'accepta; si no, l'entrada es rebutja. L'entrada d'aquests AF ??s una cadena constitu??da per s??mbols d'un alfabet i de fet es determina si aquesta cadena pertany al llenguatge que l'aut??mat reconeix. Per definici??, els llenguatges que poden acceptar els AF s??n els llenguatges regulars.

[edita] Transductors

Els transductors generen sortides basats en les entrades i/o els estats usant accions. S??n usats per aplicacions de control. Hi ha dos tipus:

M??quina de Moore
Aquests AF nom??s usen accions d'entrada, les sortides nom??s depenen de l'estat actual.
M??quina de Mealy
Aquests AF usen accions d'entrada, per tant les sortides depenen de les entrades i de l'estat actual.

[edita] Definici?? formal

Formalment, un aut??mat finit acceptador pot ser descrit com una 5-tupla (S,??,T,s,A) on:

  • ?? ??s un alfabet d'entrada (un conjut finit i no buit de s??mbols);
  • S un conjunt finit i no buit d'estats;
  • s \in S ??s l'estat inicial i element d'S; En un Aut??mat Finit no Determinsta, S0 es un conjunt d'estats inicials.
  • T ??s la funci?? de transici??: T: S \times \Sigma \to \mathcal{P}(S);
  • A \subseteq S ??s un conjunt d'estats d'acceptaci?? o finals, subconjunt d'S.

Formalment, un aut??mat finit transductor pot ser descrit com una 6-tupla (S,??,??,s,??) on:

  • ?? ??s un alfabet d'entrada (un conjut finit no buit de s??mbols);
  • ?? ??s l'alfabet de sortida (un conjunt finit no buit de s??mbols);
  • S un conjunt finit i no buit d'estats;
  • s \in S ??s l'estat inicial i element d'S; En un Aut??mat Finit no Determinsta, S0 es un conjunt d'estats inicials.
  • T ??s la funci?? de transici??: T: S \times \Sigma \to \mathcal{P}(S);
  • ?? la funci?? de sortida.

Si la funci?? de sortida ??s funci?? de l'estat i de l'alfabet d'entrada: (\omega: S \times \Sigma \to \Gamma) la definici?? corresponent a una M??quina de Mealy. Si la funci?? de sortida depen nom??s de l'estat: (\omega: S \to \Gamma) la definici?? correspon a una M??quina de Moore

Exemple (acceptador)

  • ?? = {0,1},
  • S = {S1, S2},
  • T = {(S1,0,{S2});(S1,1,{S1});(S2,0,{S1});(S2,1,{S2})}
  • s = S1
  • A = {S1}.

[edita] Formes de representar un aut??mat finit

A m??s d'anotar un AF fent servir la seva descripci?? formal, ??s possible representar-lo mitjan??ant altres anotacions que resulten mes c??modes. Les m??s usuals s??n:

  • Les Taules de Transicions: la taula de transicions per l'AF de l'exemple ??s
0
1
S1 S2 S1
S2 S1 S2


  • Els Diagrames de transicions: el diagrama de transicions per l'exemple ??s



  • Les Expressions regulars. Es demostra que donat un aut??mat d'estats finits, existeix una expressi?? regular que el representa.

?? ?? 1* ?? (1* ?? 0 ?? 1* ?? 0)*

[edita] Descripci?? informal del seu funcionament

En l'inici del proc??s de reconeixement d'una cadena d'entrada, l'AF es troba a l' estat inicial i a mida que processa cada s??mbol de la cadena va canviant l'estat d'acord amb el que hi ha determinat a la funci?? de transici??. Quan s'ha processat l'??ltim dels s??mbols de la cadena d'entrada, l'aut??mat s'atura. Si l'estat en el que s'atura ??s un estat d'acceptaci?? o final, llavors la cadena pertany al llenguatge reconegut per l'aut??mat; en cas contrari, la cadena no pertany al llenguatge.

[edita] Aut??mats finits deterministes

Uu AFD o Aut??mat Finit Determinista ??s tot aut??mat finit on els seus estats d'arribada est?? un??vocament determinat per l'estat inicial i el car??cter llegit per l'aut??mat.

??s clar que, al contrari de la definici?? d'Aut??mat finit, aquest ??s un cas particular on no es permeten transicions lamda (buides), el domini de la funci?? T ??s S (amb el qual no es permeten transicions des de un estat d'un mateix s??mbol a varis estats).

A partir d'aquest aut??mat finit ??s possible trobar l'expressi?? regular resolent un sistema d'equacions.

S1 = 1 S1 + 0 S2 + ??
S2 = 1 S2 + 0 S1

Sent ?? la paraula nul??la. Resolent el sistema i fent ??s de les reduccions apropiades s'obtenen la seg??ent expressi?? regular: 1*(01*01*)*.

Inversament, donada una expressi?? regular ??s possible generar un aut??mat que reconegui el llenguatge en q??esti?? utilitzant l'agorisme de Thompson, desenvolupat per Ken Thompson, un dels principals creadors d'UNIX, juntament amb Dennis Ritchie.

Un tipus interessant d'aut??mats finits deterministes s??n els tries .

[edita] Aut??mats finits no deterministes

Un AFN, AFND o aut??mat finit no determinista ??s aquell que presenta zero, una o m??s transicions per el mateix car??cter de l'alfabat i es classifiquen en: amb transicions ?? i sense transicions ?? depenent de l'exist??ncia o no d'una o m??s transicions sense que l'aut??mat llegeixi el proper car??cter de la cadena que esta analitzant.

Un aut??mat finit no determinista tamb?? pot o no tenir m??s d'un node inicial.

[edita] Vegeu tamb??