Formal grammar

Rules can help us make a language.

These rules are like a game. You start with one special symbol. Then, you use rules to change it. Rules turn one set of symbols into another. Some symbols are just parts of a word. Other symbols are tools to help you change things. You keep changing them until you are done. This can make many different strings. It is a way to build patterns. Rules help us see how things are made.

Imagine a set of rules for a game. You start with one special symbol. This is called a start symbol. You use rules to change your symbols into new ones. These are called production rules. Each rule has a left side and a right side. You take what is on the left and swap it for the right.

There are two kinds of symbols in this game. Some are terminal symbols. These are the final parts of a string. They do not change anymore. Other symbols are nonterminal symbols. These are tools that help you keep rewriting. You keep going until only terminal symbols are left.

Some rules are very strict. This creates different types of grammars. Noam Chomsky grouped these into a hierarchy. He found that some grammars are more powerful than others. For example, regular grammars use very simple rules. Context-free grammars use slightly more complex rules. Computer scientists use these ideas to build parsers. A parser is a tool that checks if a string follows the rules. It helps computers understand the form of a language.

Imagine you are playing a game with symbols. You start with one special symbol called a start symbol. You follow a set of rules to change these symbols into new ones. These are called production rules. Each rule has a left side and a right side. You find what is on the left and swap it for the right side.

This process is like a language generator. It creates strings of symbols following a specific pattern. A formal grammar does not care about what the symbols mean. It only cares about the form or the shape of the string. This is why it is used in math and computer science.

To understand how this works, you must know about two types of symbols. Terminal symbols are the final parts of a string. They are the end of the line and cannot be changed further. Nonterminal symbols are different because they act as tools for rewriting. You use the production rules to replace nonterminal symbols with new things. You keep doing this until only terminal symbols are left. When a string has no more nonterminal symbols, it is called a sentence. If there are many ways to make the same sentence, the grammar is called ambiguous.

In the 1950s, a thinker named Noam Chomsky changed how we look at these rules. He proposed a way to organize them called generative grammars. In 1956, he created the Chomsky hierarchy to group different types of grammars. He found that some rules are stricter than others. Some grammars are very powerful and can express many things. Other grammars have very simple rules and can only express a few things. This hierarchy helps scientists understand the limits of different systems. It shows us which languages can be built and which cannot.

There are several important levels in this hierarchy. Regular grammars are at one level and have very simple rules. They can be understood by a machine called a finite-state machine. Context-free grammars are another important type. In these, the left side of a rule has only one nonterminal symbol. These are often used to build parsers in computers. A parser is a tool that checks if a string follows the rules. Some languages are so complex that a machine cannot even recognize them. This is part of a study called automata theory.

You can see these ideas in the technology you use every day. Computer scientists use formal grammar to help machines understand code. They also use it in linguistics to study how sentences are built. Some people use a method called compositional semantics to find meaning. This involves breaking a string down into parts to see its deep structure. This structure is often shown as a parse tree. By looking at the form, we can understand how the parts fit together. It is a way to turn a messy string into a clear pattern.

A formal grammar is a mathematical system used to generate strings of symbols. It acts as a set of rules for rewriting specific symbols into every possible combination allowed by a language. Importantly, a formal grammar describes only the form or syntax of these strings. It does not describe what the strings actually mean. In applied mathematics, the study of these systems is called formal language theory. This field is essential to theoretical computer science, mathematical logic, and theoretical linguistics.

To understand the mechanism, you must look at the components of a grammar. A grammar consists of a set of nonterminal symbols and a set of terminal symbols. Nonterminal symbols are placeholders that can be replaced. Terminal symbols are the final characters that cannot be changed further. The system also includes a designated start symbol, often called the sentence symbol. The core of the system is a set of production rules. Each rule has a left-hand side and a right-hand side. To use a rule, you find the left-hand side in a string and replace it with the right-hand side.

This process creates a sequence of transformations. You begin with the single start symbol and apply rules repeatedly. If a rule replaces a string with an empty string, it is called an erasing rule. The process continues until the string contains only terminal symbols. Once all nonterminal symbols are gone, the result is called a sentence. If there are multiple different ways to generate the exact same sentence, the grammar is described as ambiguous. This ambiguity can make a grammar more complex to analyze or use in computing.

In 1956, Noam Chomsky proposed a formalization known as generative grammars. He organized these grammars into a system called the Chomsky hierarchy. This hierarchy classifies grammars based on how strict their production rules are. The more restrictions a rule has, the fewer languages that grammar can express. This classification helps scientists understand the expressive power of different systems. It allows researchers to group languages by their mathematical complexity.

One level in the hierarchy is the regular grammar, also known as Type 3. These are the most restricted grammars. In a regular grammar, the left-hand side must be a single nonterminal symbol. The right-hand side is also limited to a terminal, an empty string, or a terminal followed by a nonterminal. All languages created by regular grammars can be recognized by a finite-state machine. Another important type is the context-free grammar, or Type 2. In these, the left-hand side must be a single nonterminal symbol, but the right-hand side can be more complex. Context-free languages are widely used because parsers for them can be implemented efficiently.

Formal grammar is also used to build parsers. A parser is a computing function that determines if a string belongs to a specific language. If the string follows the rules, the parser accepts it. If not, the parser identifies it as grammatically incorrect. To describe these parsers, scientists use automata theory. This study has shown that it is impossible to design a recognizer for certain formal languages. This discovery is linked to the concept of undecidable problems in mathematics.

Grammars are also connected to how we understand meaning through compositional semantics. This practice suggests that the meaning of a string is structured by its syntax. To find the meaning, one can break a string into parts to find its analyzed form. In computer science, this is called a parse tree. In generative grammar, it is known as the deep structure. By analyzing these structures, researchers can move from the form of a string to its actual meaning. This connection links the rigid rules of math to the complex patterns of human language.