Movatterモバイル変換

Formal language

From Simple English Wikipedia, the free encyclopedia

Inmathematics,computer science andlinguistics, aformal language is one that has a particular set of symbols, and whose expressions are made according to a particular set of rules. The symbol ${\mathcal {L}}$ is often used as avariable for formal languages inlogic.^[1]

Unlikenatural languages, the symbols and formulas in formal languages aresyntactically andsemantically related to one another in a precise way.^[2] As a result, formal languages are completely (or almost completely) void ofambiguity.^[3]

Examples

[change |change source]

Some examples of formal languages include:

The set of all words over ${a,b}\,$
The set $\left\{a^{n}\right\}$ , where $n\,$ is anatural number and $a^{n}\,$ means $a\,$ repeated $n {\displaystyle n}$ times
Finite languages, such as $\{\{a,b\},\{a,aa,bba\}\}\,$
The set of syntactically correct programs in a givenprogramming language
The set of inputs upon which a certainTuring machine halts

Specification

[change |change source]

A formal language can be specified in a great variety of ways, such as:

Strings produced by someformal grammar (seeChomsky hierarchy)
Strings described or matched by aregular expression
Strings accepted by someautomaton, such as aTuring machine orfinite state automaton
Strings indicated by adecision procedure (a set of related yes/no questions) where the answer is 'yes'

Related pages

[change |change source]

Language for languages in general
Syntax for the form of a language in general
Semantics for the meanings in a language
Natural language for languages that are not formal
Computer language for application of formal languages in computing
Programming language for the application of formal languages to program computers

References

[change |change source]

↑"Comprehensive List of Logic Symbols".Math Vault. 2020-04-06. Retrieved2020-10-09.
↑"Definition of formal language | Dictionary.com".www.dictionary.com. Retrieved2020-10-09.
↑"1.11. Formal and Natural Languages — How to Think like a Computer Scientist: Interactive Edition".runestone.academy. Retrieved2020-10-09.

Other websites

[change |change source]

http://icalp06.dsi.unive.it/Archived 2006-06-09 at theWayback Machine ICALP 2006 33rd International Colloquium on Automata, Languages and Programming.
http://www.cs.auckland.ac.nz/CDMTCS/conferences/dlt/DLTConfSeries.html International Conferences on Developments in Language Theory

v
t
e

Mathematical logic

General

Theorems (list)
& Paradoxes

Logics

Traditional	Tautology Proposition Inference Logical equivalence Consistency Equiconsistency Argument Syllogism Venn diagram Classical logic Logical truth Soundness Validity Square of opposition
Propositional	Boolean algebra Propositional calculus Truth tables Boolean functions Logical connectives Propositional formula Many-valued logic 3 Finite ∞
Predicate	First-order list Second-order Monadic Higher-order Free Quantifiers Predicate Monadic predicate calculus

Set theory

Set Hereditary (Ur-)Element Ordinal number Relation Equivalence Partition Set operations: Intersection Union Complement Cartesian product Power set Identities Class Extensionality Forcing
Types ofSets	Countable Uncountable Empty Inhabited Singleton Finite Infinite Transitive Ultrafilter Recursive Fuzzy Universal Universe Constructible Grothendieck Von Neumann
Maps & Cardinality	Function/Map Domain Codomain Image In/Sur/Bi-jection Schröder–Bernstein theorem Isomorphism Gödel numbering Enumeration Large cardinal Inaccessible Aleph number Operation Binary
Set theories	Zermelo–Fraenkel Axiom of choice Continuum hypothesis General Kripke–Platek Morse–Kelley Naive New Foundations Tarski–Grothendieck Von Neumann–Bernays–Gödel Ackermann Constructive