langages formels, grammaires, théorie des automates
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...
Je pense au problème suivant: je veux trouver une expression régulière qui correspond à un ensemble particulier de chaînes (par exemple, des adresses électroniques valides) et ne correspond à aucune autre (adresses électroniques non valides). Supposons que par expression régulière, nous entendons...
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...
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...
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 |...
En parallèle, j'écris un langage en utilisant Python. J'ai commencé par utiliser un clone flex / bison appelé Ply, mais je me heurte aux limites de la puissance de ce que je peux exprimer avec ce style de grammaire, et je ne suis pas intéressé à pirater ma langue en raison d'un décalage d'impédance...
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...
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...
Nous définissons un langage d'arbre régulier comme dans le livre TATA : c'est l'ensemble d'arbres accepté par un automate d'arbre fini non déterministe (chapitre 1) ou, de manière équivalente, l'ensemble d'arbres généré par une grammaire d'arbre régulière (chapitre 2). Les deux formalismes ont des...
Étant donné une langue régulière (NFA, DFA, grammaire ou expression régulière), comment peut-on compter le nombre de mots acceptés dans une langue donnée? "Avec exactement n lettres" et "avec au plus n lettres" présentent un intérêt. Margareta Ackerman a deux articles sur le sujet connexe de...
Dans de nombreux articles impliquant des grammaires sans contexte (CFG), les exemples de telles grammaires présentés ici admettent souvent des caractérisations faciles du langage qu'elles génèrent. Par exemple: S→aaSbS→aaSbS \to a a S b S→S→S \to génère {a2ibi|i≥0}{a2ibi|i≥0}\{ a^{2i} b^i | i \geq...
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...
Je lisais récemment sur l' analyseur Earley et je pense que c'est l'un des algorithmes les plus élégants que j'ai vus à ce jour. Cependant, l'algorithme dans son sens traditionnel est un identificateur et non un analyseur, ce qui signifie qu'il peut détecter si une chaîne correspond à un CFG...
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...