请输入您要查询的字词:

 

单词 TheoryOfFormalLanguages
释义

theory of formal languages


Note: This entry is very rough at the moment, and requires work. I mainly wrote it to help motivate other entries and to organize entries on this topic and point out holes in our coverage. Right now, it is mainly a list of entries, many of which have not been written yet. Under the first heading, there is short paragraph. Eventually, there should be such a paragraph under each entry and a bibliography at the end. However, this is a lot of work for one person, so this entry is world editable in the hope that others who are knowledgable in this topic will contribute their expertise.

1 Basic concepts and terminology

Loosely speaking, a formal languageMathworldPlanetmath is a languagePlanetmathPlanetmath whose structrure can be specified with mathematical precision. The study of formal languages is not only interesting as a mathematical discipline in its own right, but also because of its relevance to the foundations of mathematics, its applications, and surprising connections with other branches of mathematics.

  • alphabet

  • automaton

  • concatenationMathworldPlanetmath

  • derivationPlanetmathPlanetmath

  • grammar

  • homomorphism of languages

  • isomorphismMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath of languages

  • language

  • abstract family of languages (AFL)

  • reversal or mirror image

  • initial symbol

  • production

  • rewriting rule

  • semantics

  • syntax

  • terminal symbol

  • non-terminal symbol

  • word

2 Classification of languages

  • Chomsky Hierarchy

  • regular language

  • context-free language

  • context-sensitive language

  • phrase-structure language

  • type-3 language

  • type-2 language

  • type-1 language

  • type-0 language

3 Regular (type 3) languages

  • regular expressionMathworldPlanetmath

  • Kleene star

  • Kleene algebra

  • left-linear grammar

  • right-linear grammar

  • finite automaton

4 Context-free (type 2) languages

  • Chomsky normal form

  • derivation tree

  • intersectionMathworldPlanetmathPlanetmath of context-free and regular languages is context-free

  • leftmost derivation

  • rightmost derivation

  • Greibach normal form

  • pumping lemmaPlanetmathPlanetmath

  • pushdown automaton

  • deterministic pushdown automaton

  • a language is context-free iff it can be recognized by a pushdown automaton

  • Earley’s algorithmMathworldPlanetmath

  • ambiguous grammar

  • LL(k) (http://planetmath.org/LLk) grammar

  • left-factored grammar

  • LR(k) (http://planetmath.org/LRk) grammar

  • every LR(k) grammar can be recognized by a deterministic pushdownautomaton

  • every language which can be recognized by a deterministic pushdownautomaton can be described by an LR(1) grammar

5 Context-sensitive (type 1) languages

  • Kuroda normal form

  • length-increasing grammar

  • a language is context-sensitive iff it can be generated by a length-increasing grammar

  • linear bounded automaton

  • a language is context-sensitive iff it can be recognized by a linear bounded automaton

6 Phrase-structure (type 0) languages

  • recursive language

  • recursively enumerable language, co-recursively enumerable language

  • language that is neither recursively enumerablePlanetmathPlanetmath, nor co-recursively enumerable

  • every phrase-structure language is recursively enumerable

7 Other types of languages and automata that describe them

  • star-free language versus aperiodic finite automaton

  • a star-free language is regularPlanetmathPlanetmathPlanetmath, but not conversely

  • mildly context-sensitive language versus embedded pushdown automaton

  • tree-adjoining grammar

  • languages generated by tree-adjoining grammars are exactly the mildly context-sensitive languages

  • a context-free language is mildly context-sensitive, but not conversely

  • indexed language versus nested stack automaton

  • a mildly context-sensitive language is indexed, but not conversely

  • an indexed language is context-sensitive, but not conversely

8 Connection to group and semigroup theory

  • finitely presented group

  • automatic groupMathworldPlanetmath

  • semi-Thue system (http://planetmath.org/SemiThueSystem)

  • Post system

  • word problem

  • Post correspondence problem

  • conjugacy problem

9 Decidability

  • membership problem

  • emptiness problem

  • recursively enumerable language

  • recursive language

10 Special languages

  • Dyck languageMathworldPlanetmath

  • derivation language

Titletheory of formal languages
Canonical nameTheoryOfFormalLanguages
Date of creation2013-03-22 15:06:37
Last modified on2013-03-22 15:06:37
Ownerrspuzio (6075)
Last modified byrspuzio (6075)
Numerical id16
Authorrspuzio (6075)
Entry typeTopic
Classificationmsc 68R15
Classificationmsc 68Q70
Classificationmsc 68Q45
Classificationmsc 68Q42
Classificationmsc 20M05
Classificationmsc 20F10
Classificationmsc 08A50
Classificationmsc 03D40
Classificationmsc 03D05
Classificationmsc 03C07
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 17:12:59