Formal Languages and Grammars

Formal Languages and Grammars

• Formal languages are used to describe the syntax of programming languages and are important in computer science.
• Examples of formal languages include predicate logic, regular languages, and programming languages like Java or PHP.

Basic Concepts

• Linguistics (the study of natural languages) provides a basis for the study of formal languages.
• Key concepts in the analysis of natural and formal languages include syntax, semantics, and pragmatics.

Syntax

• Syntax describes which words or phrases are allowed in a language.
• Syntax plays a central role in the processing of formal languages in computer science.

Semantics

• Semantics describes the meaning of words or phrases in a language.
• In a natural language, semantics involves translating words or phrases into other languages or describing them with synonymous words.
• In a programming language, semantics involves the execution of a program written in the language.

Pragmatics

• Pragmatics involves the meaning of sentences within a certain context.
• Pragmatics includes knowledge about what should not be said (e.g., expletives) and best practices for programming (e.g., variable naming conventions).

Formal Languages and Grammars

• A formal language consists of an alphabet, a finite set of symbols, and a set of production rules or grammar.
• A grammar is a set of rules that generates words in a language.
• Words in a formal language consist of symbols from the alphabet, combined according to the production rules.

Decision Problems

• Decision problems in the theory of formal languages include:
  • Word problem: Is a given word part of a language?
  • Equivalence problem: Are two grammars equivalent?
  • Emptiness problem: Is a language empty?
  • Finiteness problem: Is a language finite?

The Chomsky Hierarchy

• The Chomsky hierarchy is a classification of formal languages based on the complexity of their grammars.
• The hierarchy consists of:
  • Type-0 grammars: recursively enumerable languages
  • Type-1 grammars: context-sensitive languages
  • Type-2 grammars: context-free languages
  • Type-3 grammars: regular languages

Regular Grammars and Regular Languages

• A regular grammar is a grammar in which all production rules have one of the following forms: T → a, T → aU, or T → ε (where a is a terminal symbol, U is a nonterminal symbol, and ε is the empty string).
• Regular grammars generate regular languages.
• Regular languages can be described using regular expressions or finite automata.

Context-Free Grammars and Context-Free Languages

• A context-free grammar is a grammar in which all production rules have the form: l → r (where l is a nonterminal symbol and r is a string of terminal and nonterminal symbols).
• Context-free grammars generate context-free languages.
• Context-free languages are used to describe the syntax of programming languages.

Context-Free Grammars and Syntax Trees

• Every derivation of a word from a context-free grammar can be represented as a syntax or parse tree.
• A context-free grammar is unambiguous if every word has a unique parse tree.

The Backus-Naur Form (BNF)

• The Backus-Naur Form (BNF) is a notation for describing context-free grammars.
• BNF is used to describe the syntax of programming languages and is also used in Request for Comments (RFCs) documents.### Pumping Lemma for Context-Free Languages
• If a language L is context-free, there exists an integer m ≥ 1 such that every word z ∈ L with length ≥ m can be written as z = uvwxy with substrings u, v, w, x, y.
• The substrings v, w, and x have a combined length of at most m.
• At least one of the words v and x is nonempty.
• For every natural number n, the word uvnwxny is contained in L.

Decision Problems for Context-Free Languages

• The word problem is decidable for context-free languages.
• The emptiness and finiteness problems are also decidable for context-free languages.
• However, the equivalence problem is not decidable for context-free languages.

Context-Sensitive Languages (Type-1 Grammars)

• Context-sensitive grammars allow for more general grammars and form a larger class of languages.
• A grammar is context-sensitive if all rules are of the form uAw → uvw, where A ∈ V is a non-terminal symbol, and u, w ∈ V ∪ Σ* and v ∈ V ∪ Σ+.

Properties of Context-Sensitive Grammars

• A word cannot get shorter through the application of a rule (with the exception of S → ε).
• There is no pumping lemma for context-sensitive languages.

Decision Problems for Context-Sensitive Languages

• The word problem is decidable for context-sensitive languages.
• The emptiness, finiteness, and equivalence problems are not decidable for context-sensitive languages.

Comparison of Decision Problems

• The following table summarizes the decidability of decision problems for different types of grammars:
  • Word problem: decidable for regular, context-free, and context-sensitive languages; undecidable for type-0 grammars
  • Emptiness problem: decidable for regular and context-free languages; undecidable for context-sensitive and type-0 grammars
  • Finiteness problem: decidable for regular and context-free languages; undecidable for context-sensitive and type-0 grammars
  • Equivalence problem: decidable for regular languages; undecidable for context-free, context-sensitive, and type-0 grammars