Formal language

Imagine you have a box of letter blocks. Each block is a symbol from a set called an alphabet.

You can snap these blocks together to make a string. A string is just a sequence of letters. In a formal language, we only care about certain strings. We call these strings well-formed if they follow specific rules. These rules are known as a grammar. A grammar tells you how to build words the right way. Some strings might look right but fail the rules. A formal language is simply the set of all those correct strings.

How do these rules actually work? They focus on the shape and order of symbols. This is called syntax. Syntax is different from semantics, which is the meaning of the words. For example, a rule might say a plus sign must sit between two numbers. The string "23+4=555" follows this rule. However, the rule does not care if the math is true. It only cares if the symbols are in the right spots. This way of working lets us study the structure of language itself. We can use these rules to group different types of languages together.

Many thinkers have worked on these ideas over hundreds of years. In the 17th century, Gottfried Leibniz imagined a universal language. He wanted to use pictographs to represent all ideas. Later, Gottlob Frege tried to make this real. He wrote about a formal language of pure language in 1879 and 1893. In 1907, Leonardo Torres Quevedo used a formal language for mechanical drawings in Vienna. Between 1906 and 1914, Axel Thue published papers about words and language. He helped create what we now call Thue Systems. These thinkers helped us move from simple symbols to complex systems.

In the 20th century, these ideas became very important for computers. Noam Chomsky created the Chomsky hierarchy to group languages. This helps us see how complex a language is. In 1959, John Backus developed a way to describe programming languages. He worked on a language called FORTRAN. Peter Naur later used this method for a language called ALGOL60. Today, we use these rules to define how computers read code. We also use them to study how hard it is for machines to solve problems. This field is part of a bigger study called complexity theory.

Formal languages connect to many things you already know. You use rules every time you write a sentence in school. Computer scientists use these same ideas to build software. Even math uses them to show how symbols can be moved around. You can think of an alphabet like the letters in your ABCs. A word is just a way to put those letters in order. By using these strict rules, we can make sure machines understand us perfectly. It turns the messy way humans speak into a clear system of patterns.