Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Opérations sur les langues formelles

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 introduit le concept de langues formelles sur un alphabet, y compris les langues finies et infinies avec des motifs spécifiques. Il couvre les opérations comme l'union, l'intersection et la concaténation des langues, ainsi que l'exponentiation des langues. La séance de cours explore également la représentation des langues dans les programmes et le fonctionnement de l'étoile Kleene, fournissant des exemples et des théorèmes.

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

Concepts associés (32)

Langage formel

Un langage formel, en mathématiques, en informatique et en linguistique, est un ensemble de mots. L'alphabet d'un langage formel est l'ensemble des symboles, lettres ou lexèmes qui servent à construire les mots du langage ; souvent, on suppose que cet alphabet est fini. La théorie des langages formels a pour objectif de décrire les langages formels. Les mots sont des suites d'éléments de cet alphabet ; les mots qui appartiennent à un langage formel particulier sont parfois appelés mots bien formés ou formules bien formées.

Alphabet

thumb|Lettres de l'alphabet phénicien. Un alphabet (de alpha et bêta, les deux premières lettres de l’alphabet grec) est un système d'écriture constitué d'un ensemble de symboles dont chacun représente, par exemple, un des phonèmes d’une langue. Chacun des symboles d'un alphabet ou graphèmes, est appelé « lettre ». Dans les cas les plus simples, chaque lettre correspond à un phonème de la langue et inversement.

Latin alphabet

The Latin alphabet, also known as the Roman alphabet, is the collection of letters originally used by the ancient Romans to write the Latin language. Largely unaltered with the exception of extensions (such as diacritics), it forms the Latin script that is used to write many modern European languages, including English. With modifications, it is also used for other alphabets, such as the Vietnamese alphabet. Its modern repertoire is standardised as the ISO basic Latin alphabet.

Concaténation

Le terme concaténation (substantif féminin), du latin cum (« avec ») et catena (« chaîne, liaison »), désigne l'action de mettre bout à bout au moins deux chaînes de caractères ou de péricopes. Formellement, dans le contexte théorique des langages formels : on se donne un ensemble fini Σ, et on appelle l'ensemble des séquences d'éléments de Σ ; la concaténation est alors la loi de composition interne sur qui aux séquences et , où m et n sont des entiers naturels, associe la séquence .

Étoile de Kleene

L'étoile de Kleene, parfois appelée fermeture de Kleene ou encore fermeture itérative, est, en théorie des langages, un opérateur unaire utilisé pour décrire les langages formels. Le nom étoile vient de la notation employée, un astérisque, et Kleene de Stephen Cole Kleene qui l'a introduite. L'étoile de Kleene est l'un des trois opérateurs de base utilisés pour définir une expression rationnelle, avec la concaténation et l'union ensembliste.

Afficher plus

Séances de cours associées (25)

Opérations sur les langues formelles

Explore les opérations formelles du langage, y compris la concaténation, l'union, l'intersection et l'étoile Kleene pour la répétition du langage.

Langages formels : Concepts

Couvre les bases des langues formelles, y compris les alphabets, les mots et les langues, ainsi que des opérations comme la concaténation et l'inversion.

Langages formels : Concepts

Couvre les concepts fondamentaux des langues formelles, y compris les alphabets, les mots, les langues et l'égalité des mots.

Problèmes et langues : Langues régulières

Couvre les langues régulières, l'encodage, les alphabets, les mots, les langues, la concaténation, l'exponentiation et la fermeture itérative.

Fonctions: Définitions et notations

Couvre les généralités des fonctions, y compris la définition d'une application entre les ensembles et l'unicité des éléments dans l'ensemble d'images.

Afficher plus

Concepts associés (32)