est-il possible de minimiser les automates de refoulement?

8

est-il possible de minimiser les automates de refoulement? Si non, pourquoi? Est-ce parce que pour la minimisation, les classes d'équivalence doivent avoir un indice fini et nous ne pouvons pas le garantir pour CFG?

computability automata pushdown-automata Tom J.
la source

Réponses:

8

Malheureusement, le problème n'est pas calculable. Il est même indécidable de dire si deux PDA arbitraires sont équivalents; minimiser un PDA est encore plus difficile.

DW
la source
6

J'ai répondu essentiellement à la même question (posée plus généralement) ici .

L'argument en bref: si vous pouviez le faire, vous pourriez décider de l'universalité et de quelques autres propriétés indécidables du PDA / CFG. Par conséquent, par réduction, il ne peut y avoir un tel minimiseur.

Raphael
la source
4

Désolé, minimisez en termes de quoi?

Chaque PDA a un équivalent ayant un seul état.

Hendrik Jan
la source
Huh, c'est vrai. :) Je suppose que "la taille d'un encodage raisonnable", par exemple la table de transition. Les autres réponses fonctionneraient avec ça, non?
Raphael
2

Je ne sais pas comment minimiser la façon dont vous faites avec les automates non pushdown, mais ...

Vous pouvez convertir un CFG en PDA non? Et cette conversion selon Hopcroft n'a qu'un seul état, ce qui est très minimisé, vous ne pensez pas? Donc, tout ce que vous avez à faire est de convertir votre PDA en CFG, puis votre CFG en PDA, vous aurez un PDA à 1 état.

H_DANILO
la source
Notez qu'il s'agit d'un état minimal, mais pas d'une transition minimale. Comme le dit DW, rendre la transition et l'état minimal n'est pas calculable.
jmite
0

«minimiser» signifie généralement «minimum global» mais peut parfois faire référence à un «minimum local», auquel cas il existe des heuristiques, c'est-à-dire des stratégies pouvant entraîner une certaine réduction mais ne pas toujours trouver le minimum global. et aussi certaines classes spéciales de PDA peuvent être minimisées ou "découpées". des algorithmes d'optimisation d'apprentissage automatique à «fin non garantie», par exemple des algorithmes génétiques peuvent également être employés ici. voici deux articles sur "pousser visiblement les automates" une sous-classe. 2 exemples d'articles dans ce sens:

vzn
la source