Théorie des automates, y compris les machines abstraites, les grammaires, l'analyse syntaxique, l'inférence grammaticale, les transducteurs et les techniques à états finis
Je me suis amusé à réviser la théorie du calcul pour le plaisir et cette question me harcelait depuis un moment (drôle, je n'y ai jamais pensé lorsque j'ai appris la théorie des automates à mes études de premier cycle). Alors "pourquoi" étudions-nous exactement les automates finis déterministes et...
La hiérarchie de Chomsky (–Schützenberger) est utilisée dans les manuels d'informatique théorique, mais elle ne couvre évidemment qu'une très petite fraction des langages formels (REG, CFL, CSL, RE) par rapport au diagramme de complexité complet . La hiérarchie joue-t-elle un rôle dans la recherche...
Les ordinateurs réels ont une mémoire limitée et seulement un nombre fini d'états. Donc, ce sont essentiellement des automates finis. Pourquoi les informaticiens théoriques utilisent-ils les machines de Turing (et d’autres modèles équivalents) pour étudier les ordinateurs? Quel est l'intérêt...
J'ai récemment entendu ceci: "Une machine non déterministe n'est pas la même chose qu'une machine probabiliste. En gros, une machine non déterministe est une machine probabiliste dans laquelle les probabilités de transitions ne sont pas connues". Je me sens comme si je comprends le point mais je...
Il existe toujours un moyen d’appliquer dans des domaines liés à l’informatique théorique. Mais les manuels scolaires et les cours de premier cycle n'expliquent généralement pas pourquoi la théorie des automates est un sujet important et si elle a encore des applications dans la pratique. Par...
Demandez même à une personne ayant une formation en informatique ce qu’est une expression régulière et la réponse ira probablement au-delà de la contrainte d’être à la portée d’un automate à états finis. Par exemple, l'expression «expression régulière» /^1?$|^(11+?)\1+$/ créé par une personnalité...
J'ai besoin d'un livre de théorie des automates finis avec beaucoup d'exemples que je peux utiliser pour l'auto-apprentissage et pour préparer les
Dans la préface de ses livres très influents Automates, Langages et Machines (Volumes A, B), Samuel Eilenberg a promis de façon alléchante les Volumes C et D traitant "d'une hiérarchie (appelée hiérarchie rationnelle) des phénomènes non rationnels ... utilisant des relations rationnelles comme un...
Il est bien connu qu'une expression régulière peut être reconnue par un automate fini non déterministe de taille proportionnelle à l'expression régulière, ou par une FA déterministe qui est potentiellement exponentiellement plus grande. De plus, étant donné une chaîne et une expression régulière ,...
La langue est-elle { } hors contexte ou non?aibjck | i≠j,i≠k,j≠kaibjck | i≠j,i≠k,j≠ka^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k J'ai réalisé que j'ai rencontré presque toutes les variantes de cette question avec des conditions différentes sur la relation entre i, j et k, mais pas celle-ci. Je...
Je me demandais s'il y avait un `` meilleur '' algorithme (j'expliquerai dans quel sens) pour partir d'un DFA et construire une expression régulière r telle que L ( A ) = L ( r ) , que celle du livre de Hopcroft et Ullman (1979). Dans ce document, les ensembles R k i j sont utilisés pour...
Fixe un entier nnn et un alphabet Σ = { 0 , 1 }Σ={0,1}\Sigma=\{0,1\} . Définissez D FA ( n )DFA(n)DFA(n) comme la collection de tous les automates à états finis sur nnn états avec l'état de départ 1. Nous considérons tous les DFA (pas seulement ceux connectés, minimaux ou non dégénérés); ainsi |...
Considérons un automate fini non déterministe et une fonction . De plus, nous définissons .A=(Q,Σ,δ,q0,F)A=(Q,Σ,δ,q0,F)A = (Q, \Sigma, \delta, q_0, F)f(n)f(n)f(n)Σ≤k=⋃i≤kΣiΣ≤k=⋃i≤kΣi\Sigma^{\leq k} = \bigcup_{i \leq k} \Sigma^i Analysons maintenant la déclaration suivante: Si , alors...
Je ne peux pas penser à un tel modèle, peut-être une forme de calcul lambda typé? un automate cellulaire élémentaire? Cela réfuterait presque le «principe d'équivalence informatique» de Wolfram: Presque tous les processus qui ne sont évidemment pas simples peuvent être considérés comme des calculs...
L'intersection de deux DFA (minimes) avec n états peut être calculée en utilisant O (n 2 ) temps et espace. Ceci est optimal en général, car le DFA résultant (minimal) peut avoir n 2 états. Cependant, si le DFA minimal résultant a z états, où z = O (n), peut-il être calculé dans l'espace n 2-eps ,...
1) Quelle est, le cas échéant, la relation entre le typage statique et les grammaires formelles? 2) En particulier, serait-il possible pour un automate borné linéaire de vérifier si, disons, un programme C ++ ou SML était bien typé? Un automate de pile imbriqué? 3) Existe-t-il un moyen naturel...
Pour toute langue sur , définissez En d'autres termes, constituée de tous pour lesquels il existe un de longueur égale de telle sorte que .LLLΣ∗Σ∗\Sigma^*L1 / 2= { x ∈ Σ∗: x y∈ L , y∈ Σ| x |} .L1/2={X∈Σ∗:Xy∈L,y∈Σ|X|}.L_{1/2} = \{x \in \Sigma^* : xy\in L, y\in\Sigma^{|x|} \}.L1 / 2L1/2L_{1/2}XXxyyyx...
Étant donné deux chaînes x et y, je veux créer une taille minimale DFA qui accepte x et rejette y. Une façon de le faire est la recherche par force brute. Vous énumérez les DFA en commençant par le plus petit. Vous essayez chaque DFA jusqu'à ce que vous en trouviez un qui accepte x et rejette y. Je...
Soit deux langues régulières données par les NFA en entrée.M 1 , M 2L1,L2L1,L2L_1,L_2M1,M2M1,M2M_1,M_2 Supposons que nous souhaitons vérifier si . Cela peut clairement être fait par un algorithme quadratique qui calcule l'automate produit de , mais je me demandais si quelque chose de plus efficace...
Pour un alphabet fini fixe , un langage formel sur est régulier s'il existe un automate fini déterministe (DFA) sur qui accepte exactement .L ΣΣΣ\SigmaLLLΣΣ\SigmaLΣΣ\SigmaLLL Je m'intéresse aux langues qui sont "presque" régulières dans le sens où elles peuvent être reconnues par des familles...