Since Chomsky established the description of formal language in 1956, the theory of formal language has developed rapidly. This theory has a far-reaching impact on computer science, especially on programming languages, compilation methods and computational complexity.
Chomsky divides grammar into four types, namely type 0, 1 type, type 2 and type 3. The difference between these types of grammars is that they impose different restrictions on production.
The grammar of words in most programming languages can be described by regular grammar or type 3 grammar.
Brief introduction of Chomsky:
American linguist Noam Chomsky is the founder of transformational generative grammar. 1928 was born in Philadelphia, Pennsylvania, USA on February 7th.
From 65438 to 0947, under the influence of Harris, he began to study linguistics. 195 1 completed his master's thesis "Modern Hebrew Morpheme Phonology" at the University of Pennsylvania, and 1955 completed his doctoral thesis "Transformation Analysis" and obtained his doctorate.
Chomsky remembers that his first article was written at the age of 10, which was about the threat of the spread of Nazism after the fall of Barcelona. From the age of 12 or 13, Chomsky identified with anarchism more thoroughly.