SafekipediaFormal language
Adapted from Wikipedia Β· Adventurer experience
Formal language
In logic, mathematics, computer science, and linguistics, a formal language is a special kind of language. It is made up of strings of symbols. These symbols come from a set called an "alphabet". When these symbols are put together in certain ways, they form strings, also called "words".
Formal languages are important in computer science. They help define how programming languages work. They are also used to study how hard it is for computers to understand and process information. In mathematics and logic, formal languages help us understand the rules and structure of mathematical systems.
The study of formal languages looks at their patterns and structures. It does not worry too much about their meanings. This idea came from the study of natural languages. It helps us see the rules that govern how words and sentences are built.
History
In the 1600s, a thinker named Gottfried Leibniz imagined a special way to write ideas using simple pictures. Later, a scientist named Carl Friedrich Gauss studied special codes called Gauss codes.
In the 1800s, George Boole showed how to use symbols to describe logical thinking. Another thinker, Gottlob Frege, tried to create a clear system of symbols to express ideas.
In the early 1900s, many smart people worked on formal languages. Axel Thue wrote about words and patterns, and Leonardo Torres Quevedo made a system to describe machines. Later, Noam Chomsky created a way to organize different kinds of languages, and John Backus developed a method to describe computer programming languages.
Words over an alphabet
Main article: Alphabet (formal languages)
In the study of formal languages, an alphabet is a group of symbols or letters. We can use these symbols to make words by putting them together in a line. A word is just a line of symbols from the alphabet.
For any alphabet, there is one special word with no symbols at all. This is called the empty word. When we put two words together, we get a new word with all the symbols from both words.
Definition
A formal language is a set of special strings made from symbols called an "alphabet." These strings are created by putting the symbols together in specific ways. For example, if the alphabet has the symbols A, B, and C, then "ABC" and "BAA" might be part of the language, while "CAD" might not be.
In subjects like computer science and math, people often just say "language" instead of "formal language" when the symbols are clear. Some formal languages have special rules, like regular languages or context-free languages, but the basic idea is a group of strings made from a given alphabet.
Examples
This section talks about a special kind of language used in math and computers. Imagine you have symbols, like the numbers 0 to 9, plus "+" and "=". These symbols can be put together in certain ways to make strings, or words.
Some rules decide which strings belong to this special language. For example, the string "23+4=555" follows the rules, but "=234+" does not. These rules only describe how the strings look, not what they mean. For instance, the rule does not say that "0" means the number zero or that "+" means addition.
Constructions
For small sets of words, we can list them all. But for bigger sets, there are too many words to list. Instead, we use special ways to describe them. For example, we might say a language includes all words made from the symbol "a", like "a", "aa", "aaa", and so on. Other examples include the correct programs in a programming language or all possible inputs that a computer can understand.
Language-specification formalisms
Formal languages are useful in many areas of study. They help us understand how to describe groups of strings, which are sequences of symbols.
A formal language can be defined in different ways, such as through rules called grammars, patterns called regular expressions, or machines that can recognize certain strings. We study how powerful these different ways are, how easy it is to tell if a string belongs to a language, and how we can compare different languages. Sometimes, answering these questions can be very difficult! This is why formal languages are linked to the study of what computers can and cannot do.
Operations on languages
We can do different things with groups of words made from sets of symbols. Some common actions include putting words together, finding words that appear in more than one group, and looking at words that donβt appear in a certain group.
For example, if we have two groups of words, we can join them together to make new words. We can also find words that are in both groups, or look at all possible words that are not in a certain group. These actions help us understand how different groups of words relate to each other.
concatenation Kleene star String homomorphism string operations closure properties context-free languages regular languages trios abstract families of languages
| Operation | Regular | DCFL | CFL | IND | CSL | Recursive | RE | |
|---|---|---|---|---|---|---|---|---|
| Union | L 1 βͺ L 2 = { w β£ w β L 1 β¨ w β L 2 } {\displaystyle L_{1}\cup L_{2}=\{w\mid w\in L_{1}\lor w\in L_{2}\}} | Yes | No | Yes | Yes | Yes | Yes | Yes |
| Intersection | L 1 β© L 2 = { w β£ w β L 1 β§ w β L 2 } {\displaystyle L_{1}\cap L_{2}=\{w\mid w\in L_{1}\land w\in L_{2}\}} | Yes | No | No | No | Yes | Yes | Yes |
| Complement | Β¬ L 1 = { w β£ w β L 1 } {\displaystyle \neg L_{1}=\{w\mid w\not \in L_{1}\}} | Yes | Yes | No | No | Yes | Yes | No |
| Concatenation | L 1 β L 2 = { w z β£ w β L 1 β§ z β L 2 } {\displaystyle L_{1}\cdot L_{2}=\{wz\mid w\in L_{1}\land z\in L_{2}\}} | Yes | No | Yes | Yes | Yes | Yes | Yes |
| Kleene star | L 1 β = { Ξ΅ } βͺ { w z β£ w β L 1 β§ z β L 1 β } {\displaystyle L_{1}^{*}=\{\varepsilon \}\cup \{wz\mid w\in L_{1}\land z\in L_{1}^{*}\}} | Yes | No | Yes | Yes | Yes | Yes | Yes |
| (String) homomorphism h {\displaystyle h} | h ( L 1 ) = { h ( w ) β£ w β L 1 } {\displaystyle h(L_{1})=\{h(w)\mid w\in L_{1}\}} | Yes | No | Yes | Yes | No | No | Yes |
| Ξ΅-free (string) homomorphism h {\displaystyle h} | h ( L 1 ) = { h ( w ) β£ w β L 1 } {\displaystyle h(L_{1})=\{h(w)\mid w\in L_{1}\}} | Yes | No | Yes | Yes | Yes | Yes | Yes |
| Substitution Ο {\displaystyle \varphi } | Ο ( L 1 ) = β Ο 1 β― Ο n β L 1 Ο ( Ο 1 ) β β¦ β Ο ( Ο n ) {\displaystyle \varphi (L_{1})=\bigcup _{\sigma _{1}\cdots \sigma _{n}\in L_{1}}\varphi (\sigma _{1})\cdot \ldots \cdot \varphi (\sigma _{n})} | Yes | No | Yes | Yes | Yes | No | Yes |
| Inverse homomorphism h β 1 {\displaystyle h^{-1}} | h β 1 ( L 1 ) = β w β L 1 h β 1 ( w ) {\displaystyle h^{-1}(L_{1})=\bigcup _{w\in L_{1}}h^{-1}(w)} | Yes | Yes | Yes | Yes | Yes | Yes | Yes |
| Reverse | L R = { w R β£ w β L } {\displaystyle L^{R}=\{w^{R}\mid w\in L\}} | Yes | No | Yes | Yes | Yes | Yes | Yes |
| Intersection with a regular language R {\displaystyle R} | L β© R = { w β£ w β L β§ w β R } {\displaystyle L\cap R=\{w\mid w\in L\land w\in R\}} | Yes | Yes | Yes | Yes | Yes | Yes | Yes |
Applications
Programming languages
Main articles: Syntax (programming languages) and Compiler-compiler
In programming, special rules help computers understand code. A tool called a lexical analyzer finds important parts like words and numbers. Another tool, called a parser, checks if the code is in the right order. If it is, the computer can run the code.
Formal theories, systems, and proofs
Main articles: Theory (mathematical logic) and Formal system
In math and logic, a formal theory is a group of sentences made with a special language. A formal system uses this language and rules to make new sentences. These systems help us see which statements are true.
Interpretations and models
Main articles: Formal semantics (logic), Interpretation (logic), and Model theory
Even though formal languages use symbols, we can give them meaning. In math, we study how to understand what these symbols mean and when a statement is true.
Related articles
This article is a child-friendly adaptation of the Wikipedia article on Formal language, available under CC BY-SA 4.0.