
Contents
-
-
-
-
-
-
-
9.1 Introduction 9.1 Introduction
-
9.2 Basic Concepts 9.2 Basic Concepts
-
9.2.1 Alphabets, Strings, and Languages 9.2.1 Alphabets, Strings, and Languages
-
9.2.2 Language Operations 9.2.2 Language Operations
-
9.2.3 Grammars 9.2.3 Grammars
-
9.2.4 Automata 9.2.4 Automata
-
9.2.5 Derivation Trees 9.2.5 Derivation Trees
-
-
9.3 The Chomsky Hierarchy 9.3 The Chomsky Hierarchy
-
9.3.1 Types of Grammars 9.3.1 Types of Grammars
-
9.3.2 RE Languages, Type 0 Grammars, and Turing Machines 9.3.2 RE Languages, Type 0 Grammars, and Turing Machines
-
9.3.3 CS Languages, Type 1 Grammars, and Linear Bounded Automata 9.3.3 CS Languages, Type 1 Grammars, and Linear Bounded Automata
-
9.3.4 CF Languages, Type 2 Grammars, and Pushdown Automata 9.3.4 CF Languages, Type 2 Grammars, and Pushdown Automata
-
9.3.5 REG Languages, Type 3 Grammars, and Finite-State Automata 9.3.5 REG Languages, Type 3 Grammars, and Finite-State Automata
-
9.3.6 Closure Properties 9.3.6 Closure Properties
-
-
9.4 Location of Natural Languages in the Chomsky Hierarchy 9.4 Location of Natural Languages in the Chomsky Hierarchy
-
9.4.1 Beyond Context-Free 9.4.1 Beyond Context-Free
-
9.4.2 Mild Context-Sensitivity 9.4.2 Mild Context-Sensitivity
-
9.4.3 Generative Devices beyond Context-Free 9.4.3 Generative Devices beyond Context-Free
-
-
9.5 Learning Formal Languages 9.5 Learning Formal Languages
-
9.5.1 Grammatical Inference 9.5.1 Grammatical Inference
-
9.5.2 Formal Models of Language Learning 9.5.2 Formal Models of Language Learning
-
-
Further Reading and Relevant Resources Further Reading and Relevant Resources
-
References References
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
9 Mathematical Foundations: Formal Grammars and Languages
Get accessLeonor Becerra-Bonache is Associate Professor at Aix-Marseille University (France). She works in the Natural Language Processing team (TALEP) at the Computer Science and Systems Laboratory. She obtained her European PhD Degree at Rovira i Virgili University (Spain). Her post-doctoral training includes a two-year stay at the Department of Computer Science at Yale University (USA) as a Marie Curie Researcher. Her work is in the intersection of Machine Learning, Natural Language Processing, Computer Vision, and Linguistics. Her research goal is to develop computational systems that learn to understand and speak natural languages from multimodal data, inspired in the way children learn their native language.
Gemma Bel-Enguix has a PhD in Linguistics from Universitat Rovira i Virgili and has been post-doctoral and research fellow at Georgetown, Milano-Bicocca, Aix-Marseille, and Rovira i Virgili. She works in a multidisciplinary area involving computer science, biology, and linguistics, developing models of natural computing for approaching problems of natural language. Currently, she is a researcher at the Universidad Nacional Autónoma de México. Her research is focused on theoretical models of Natural Language Processing, and the study of language from the perspective of Complex Systems.
M. Dolores Jiménez-López is an Associate Professor in the Departament de Filologies Romaniques at the Universitat Rovira i Virgili (Tarragona, Spain). She has a PhD in linguistics. She worked for two years, as a pre-doctoral fellow, at the Computer and Automation Research Institute of the Hungarian Academy of Sciences in Budapest (Hungary). Her post-doctoral training includes a three-year stay at the Department of Computer Science in University of Pisa (Italy). The application of formal models to natural language analysis is one of her main research topics.
Carlos Martín-Vide is Professor at Universitat Rovira i Virgili, Tarragona. His research areas include automata and language theory, molecular computing, theoretical computer science, and mathematical and computational linguistics, and he is (co-)author of more than 300 papers. He has been involved in the definition, operation, and monitoring of several European funding initiatives in support of fundamental research in mathematics and computer science.
-
Published:05 February 2018
Cite
Abstract
This chapter provides an overview of classical formal language theory. The text is focused on the definition of the fundamental concepts of language, grammar, and automata, and introduces some basic related notions. We also present the hierarchical classification of formal grammars proposed by N. Chomsky in the 1950s, known as the Chomsky hierarchy. The location of natural languages in this hierarchy is also discussed, together with the concept of Mildly Context Sensitivity. In the last part of the chapter, other formalisms that have interesting linguistic and computational properties are briefly introduced. The chapter concludes with a short review of grammatical inference, a subfield of machine learning that deals with the process of learning grammars and languages from data.
Sign in
Personal account
- Sign in with email/username & password
- Get email alerts
- Save searches
- Purchase content
- Activate your purchase/trial code
- Add your ORCID iD
Purchase
Our books are available by subscription or purchase to libraries and institutions.
Purchasing informationMonth: | Total Views: |
---|---|
October 2022 | 18 |
November 2022 | 17 |
December 2022 | 13 |
January 2023 | 24 |
February 2023 | 22 |
March 2023 | 7 |
April 2023 | 5 |
May 2023 | 6 |
June 2023 | 16 |
July 2023 | 11 |
August 2023 | 15 |
September 2023 | 4 |
October 2023 | 14 |
November 2023 | 19 |
December 2023 | 7 |
January 2024 | 11 |
February 2024 | 5 |
March 2024 | 25 |
April 2024 | 14 |
May 2024 | 15 |
June 2024 | 11 |
July 2024 | 15 |
August 2024 | 17 |
September 2024 | 17 |
October 2024 | 11 |
November 2024 | 7 |
December 2024 | 6 |
January 2025 | 8 |
February 2025 | 2 |
March 2025 | 14 |
April 2025 | 4 |
Get help with access
Institutional access
Access to content on Oxford Academic is often provided through institutional subscriptions and purchases. If you are a member of an institution with an active account, you may be able to access content in one of the following ways:
IP based access
Typically, access is provided across an institutional network to a range of IP addresses. This authentication occurs automatically, and it is not possible to sign out of an IP authenticated account.
Sign in through your institution
Choose this option to get remote access when outside your institution. Shibboleth/Open Athens technology is used to provide single sign-on between your institution’s website and Oxford Academic.
If your institution is not listed or you cannot sign in to your institution’s website, please contact your librarian or administrator.
Sign in with a library card
Enter your library card number to sign in. If you cannot sign in, please contact your librarian.
Society Members
Society member access to a journal is achieved in one of the following ways:
Sign in through society site
Many societies offer single sign-on between the society website and Oxford Academic. If you see ‘Sign in through society site’ in the sign in pane within a journal:
If you do not have a society account or have forgotten your username or password, please contact your society.
Sign in using a personal account
Some societies use Oxford Academic personal accounts to provide access to their members. See below.
Personal account
A personal account can be used to get email alerts, save searches, purchase content, and activate subscriptions.
Some societies use Oxford Academic personal accounts to provide access to their members.
Viewing your signed in accounts
Click the account icon in the top right to:
Signed in but can't access content
Oxford Academic is home to a wide variety of products. The institutional subscription may not cover the content that you are trying to access. If you believe you should have access to that content, please contact your librarian.
Institutional account management
For librarians and administrators, your personal account also provides access to institutional account management. Here you will find options to view and activate subscriptions, manage institutional settings and access options, access usage statistics, and more.