Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Language equation
Résumé
Language equations are mathematical statements that resemble numerical equations, but the variables assume values of formal languages rather than numbers. Instead of arithmetic operations in numerical equations, the variables are joined by language operations. Among the most common operations on two languages A and B are the set union A ∪ B, the set intersection A ∩ B, and the concatenation A⋅B. Finally, as an operation taking a single operand, the set A* denotes the Kleene star of the language A. Therefore language equations can be used to represent formal grammars, since the languages generated by the grammar must be the solution of a system of language equations.
Ginsburg and Rice
gave an alternative definition of context-free grammars by language equations. To every context-free grammar , is associated a system of equations in variables . Each variable is an unknown language over and is defined by the equation where , ..., are all productions for . Ginsburg and Rice used a fixed-point iteration argument to show that a solution always exists, and proved that i.e. any other solution must be a of this one.
For example, the grammar
corresponds to the equation system
which has as solution every superset of .
Language equations with added intersection analogously correspond to conjunctive grammars.
Brzozowski and Leiss studied left language equations where every concatenation is with a singleton constant language on the left, e.g. with variable , but not nor . Each equation is of the form with one variable on the right-hand side. Every nondeterministic finite automaton has such corresponding equation using left-concatenation and union, see Fig. 1. If intersection operation is allowed, equations correspond to alternating finite automata.
Baader and Narendran studied equations using left-concatenation and union and proved that their satisfiability problem is EXPTIME-complete.
Conway proposed the following problem: given a constant finite language , is the greatest solution of the equation always regular? This problem was studied by Karhumäki and Petre who gave an affirmative answer in a special case.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.