Séance de cours

Des expressions régulières aux automatismes

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Dans cours

CS-320: Computer language processing

We teach the fundamental aspects of analyzing and interpreting computer languages, including the techniques to build compilers. You will build a working compiler from an elegant functional language into machine code using a popular backend called LLVM (htt ...

Description

Cette séance de cours couvre la transition des expressions régulières aux automates finis, expliquant comment écrire un lexer avec différentes classes de jetons, le concept d'automates finis, les nombres avec des points décimaux, les types d'automates à états finis, permettant des transitions indéfinies et epsilon, et la conversion des NFA en DFA. Il explore également les constructions récursives, la relation entre les expressions régulières et les automates, et le processus de conversion des NFA en DFA, y compris des exemples et des clarifications.

Enseignant·e

Viktor Kuncak

Viktor Kunčak joined EPFL in 2007, after receiving a PhD degree from MIT. Since then has been leading the Laboratory for Automated Reasoning and Analysis and supervised at least 12 completed PhD theses. His works on languages, algorithms and systems for verification and automated reasoning. He served as an initiator and one of the coordinators of a European network (COST action) in the area of automated reasoning, verification, and synthesis. In 2012 he received a 5-year single-investigator European Research Council (ERC) grant of 1.5M EUR. His invited talks include those at Lambda Days, Scala Days, NFM, LOPSTR, SYNT, ICALP, CSL, RV, VMCAI, and SMT. A paper on test generation he co-authored received an ACM SIGSOFT distinguished paper award at ICSE. A PLDI paper he co-authored was published in the Communications of the ACM as a Research Highlight article. His Google Scholar profile reports an over-approximate H-index of 38. He was an associate editor of ACM Transactions on Programming Languages and Systems (TOPLAS) and served as a co-chair of conferences on Computer-Aided Verification (CAV), Formal Methods in Computer Aided Design (FMCAD), Workshop on Synthesis (SYNT), and Verification, Model Checking, and Abstract Interpretation (VMCAI). At EPFL he teaches courses on functional and parallel programming, compilers, and verification. He has co-taught the MOOC "Parallel Programming" that was visited by over 100'000 learners and completed by thousands of students from all over the world.

Source officielle

Proximité ontologique

Informatique théorique

Theory of computation: Théorie des automates

Concepts associés (32)

Automate fini inambigu

upright=1.5|thumb|Un automate fini inambigu à n+1 états reconnaissant les mots qui ont un a en position n depuis la fin. Un automate déterministe équivalent a au moins états En théorie des automates, un automate fini inambigu (on dit aussi non ambigu, en anglais , abrégé en UFA) est un automate fini non déterministe d'un type particulier. C'est un automate qui, pour chaque mot accepté, ne possède qu'un seul calcul réussi. Tout automate fini déterministe est inambigu, mais la réciproque est fausse.

Théorie des automates

En informatique théorique, l'objectif de la théorie des automates est de proposer des modèles de mécanismes mathématiques qui formalisent les méthodes de calcul.

Automate fini déterministe

Un automate fini déterministe, parfois abrégé en AFD (en anglais deterministic finite automaton, abrégé en DFA) est un automate fini dont les transitions à partir de chaque état sont déterminées de façon unique par le symbole d'entrée. Un tel automate se distingue ainsi d'un automate fini non déterministe, où au contraire plusieurs possibilités de transitions peuvent exister simultanément pour un état et un symbole d'entrée donné.

Automate fini non déterministe

Un automate fini (on dit parfois, par une traduction littérale de l'anglais, machine à états finis, au lieu de machine avec un nombre fini d'états ou machine à états finie ou machine finie à états), finite-state automaton ou finite-state machine (FSA, FSM), est une machine abstraite qui est un outil fondamental en mathématiques discrètes et en informatique. On les retrouve dans la modélisation de processus, le contrôle, les protocoles de communication, la vérification de programmes, la théorie de la calculabilité, dans l'étude des langages formels et en compilation.

Automate quantique

En informatique quantique et en informatique théorique, un automate fini quantique est une généralisation des automates finis où un mot est accepté selon le résultat d'une certaine mesure. Il existe plusieurs modèles des automates finis quantiques ; le plus restrictif est celui des automates dits « measure-once » de ; un autre est celui des automates « measure-many » de . Ces deux modèles sont très différents l'un de l’autre ; le modèle « measure-once » se rapproche plus de la théorie classique des automates finis.

Afficher plus

Séances de cours associées (58)

Expressions régulières (Récapitulatif)

Couvre les principes fondamentaux des expressions régulières et comprend des exercices sur la définition des langues.

Finite Automata: Expressions régulières et Automaton Finite Déterministe

Couvre la conversion d'automates finis à des expressions régulières et des exercices sur la construction d'automates finis déterministes.

Finite Automata: Bases

Introduit les bases des automates finis, y compris les types déterministes et non déterministes, les expressions régulières et les critères d'acceptation.

Finite Automata: Récapitulation et détermination

Couvre une récapitulation des APN et introduit le processus de détermination.

Automata fini : DFA à Expression régulière

Explique la transformation dun DFA à une expression régulière et discute des concepts importants dans la théorie des automates.

Afficher plus

Concepts associés (32)

Automate fini inambigu

Théorie des automates

En informatique théorique, l'objectif de la théorie des automates est de proposer des modèles de mécanismes mathématiques qui formalisent les méthodes de calcul.

Automate fini déterministe

Automate fini non déterministe

Automate quantique

Afficher plus