Editing Formal language (section)

== History ==
{{Expand section|date=March 2021}}
In the 17th century, [[Gottfried Leibniz]] imagined and described the [[characteristica universalis]], a universal and formal language which utilised [[pictographs]]. Later, [[Carl Friedrich Gauss]] investigated the problem of [[Gauss notation|Gauss codes]].<ref>{{cite web |url=https://www.researchgate.net/publication/220530857 |title=In the prehistory of formal language theory: Gauss Languages |date=January 1992 |access-date=30 April 2021}}</ref>

[[Gottlob Frege]] attempted to realize Leibniz's ideas, through a notational system first outlined in ''[[Begriffsschrift]]'' (1879) and more fully developed in his 2-volume Grundgesetze der Arithmetik (1893/1903).<ref>{{cite web |url=https://plato.stanford.edu/entries/frege/ |title=Gottlob Frege |date=5 December 2019 |access-date=30 April 2021}}</ref> This described a "formal language of pure language."<ref name="Herken1279">{{cite book|editor=Rolf Herken|title=The universal Turing machine: a half-century survey|chapter-url=https://books.google.com/books?id=YafIDVd1Z68C&pg=PA290|year=1995|publisher=Springer|isbn=978-3-211-82637-9|page=290|chapter=Influences of Mathematical Logic on Computer Science|author=Martin Davis}}</ref>

In the first half of the 20th century, several developments were made with relevance to formal languages. [[Axel Thue]] published four papers relating to words and language between 1906 and 1914. The last of these introduced what [[Emil Post]] later termed 'Thue Systems', and gave an early example of an [[undecidable problem]].<ref>{{cite web |url=https://core.ac.uk/download/pdf/297029993.pdf |archive-url=https://web.archive.org/web/20210430011129/https://core.ac.uk/download/pdf/297029993.pdf |archive-date=2021-04-30 |url-status=live |title=Thue's 1914 paper: a translation |date=28 August 2013 |access-date=30 April 2021}}</ref> Post would later use this paper as the basis for a 1947 proof "that the word problem for semigroups was recursively insoluble",<ref>{{cite web |url=https://mathshistory.st-andrews.ac.uk/Biographies/Post/ |title=Emil Leon Post |date=September 2001 |access-date=30 April 2021}}</ref> and later devised the [[Post canonical system|canonical system]] for the creation of formal languages.

In 1907, [[Leonardo Torres Quevedo]] introduced a formal language for the description of mechanical drawings (mechanical devices), in [[Vienna]]. He published "Sobre un sistema de notaciones y símbolos destinados a facilitar la descripción de las máquinas" ("On a system of notations and symbols intended to facilitate the description of machines").<ref>Torres Quevedo, Leonardo. [https://quickclick.es/rop/pdf/publico/1907/1907_tomoI_1634_01.pdf Sobre un sistema de notaciones y símbolos destinados a facilitar la descripción de las máquinas, (pdf)], pp. 25–30, Revista de Obras Públicas, 17 January 1907.</ref> [[Heinz Zemanek]] rated it as an equivalent to a [[programming language]] for the numerical control of machine tools.<ref name=Bruderer>{{Cite book|chapter-url=https://books.google.com/books?id=Gh8SEAAAQBAJ&dq=leonardo+torres+quevedo+heinz+zemanek+formal+language&pg=PA1212|title=Milestones in Analog and Digital Computing|last=Bruderer|first=Herbert|date=2021|publisher=Springer|isbn=978-3030409739|page=1212|chapter=The Global Evolution of Computer Technology|language=en}}</ref>

[[Noam Chomsky]] devised an abstract representation of formal and natural languages, known as the [[Chomsky hierarchy]].<ref>{{cite journal |last1=Jager |first1=Gerhard |last2=Rogers |first2=James |date=19 July 2012 |title=Formal language theory: refining the Chomsky hierarchy |journal=Philosophical Transactions of the Royal Society B |volume=367 |issue=1598 |pages=1956–1970 |doi=10.1098/rstb.2012.0077|pmid=22688632 |pmc=3367686 }}</ref> In 1959 [[John Backus]] developed the Backus-Naur form to describe the syntax of a high level programming language, following his work in the creation of [[FORTRAN]].<ref>{{cite web |url=https://mathshistory.st-andrews.ac.uk/Biographies/Backus/ |title=John Warner Backus |date=February 2016 |access-date=30 April 2021}}</ref> [[Peter Naur]] was the secretary/editor for the ALGOL60 Report in which he used [[Backus–Naur form]] to describe the Formal part of ALGOL60.