"In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules can be applied to a nonterminal symbol regardless of its context."
Context-free languages are a type of language that can be recognized by a pushdown automaton (PDA) or a non-deterministic pushdown automaton (NPDA).
Formal Languages: This topic introduces the concept of formal languages, which are used to represent natural languages or programming languages. It also covers the properties of formal languages and their classification.
Chomsky Hierarchy: This topic explains the Chomsky hierarchy, which is a classification of formal languages based on the grammars used to generate them. It also includes the different types of grammars and their relationship to the corresponding language class.
Context-Free Grammars: A context-free grammar is a formal definition of a language in terms of its constituent syntactic structures. This topic explores the properties of context-free grammars, their representation and the concept of a parse tree.
Parse Trees: This topic explains the concept of parse trees, the role they play in the parsing process for context-free languages, and how they are constructed.
Parsing Algorithms: This topic covers the different parsing algorithms used to derive parse trees from context-free grammars. It includes top-down parsing algorithms such as LL and recursive descent parsing, as well as bottom-up parsing methods, such as LR parsing.
Ambiguity in Context-Free Grammars: Context-free grammars can generate ambiguous languages, which means that the same input string can have multiple valid parse trees. This topic discusses the sources of ambiguity in context-free grammars and how they can be resolved.
Normal Forms: Normal forms are a way to standardize context-free grammars and make them easier to analyze. This topic covers the different normal forms for context-free grammars, such as Chomsky Normal Form and Greibach Normal Form.
Pumping Lemma: The pumping lemma is a powerful tool for proving that certain languages are not context-free. This topic covers the pumping lemma for context-free languages and how it can be used to show that a language is not context-free.
Applications of Context-Free Languages: This topic explores the application of context-free languages in programming languages, compilers, and natural language processing. It includes the role of context-free grammars in lexical analysis, syntactic analysis, and semantic analysis.
Pushdown Automata: Pushdown automata are a type of formal machine used to recognize context-free languages. This topic covers the properties of pushdown automata, their relationship to context-free grammars, and how they can be used to recognize context-free languages.
Regular language: Regular languages are the type of formal languages that can be recognized by regular expressions or finite automata. They are limited in their expressive power.
Context-free language: Context-free languages are the type of formal languages that can be recognized by pushdown automata. They are more expressive than regular languages.
Context-sensitive language: Context-sensitive languages are the type of formal languages that can be recognized by linear-bounded automata. They are even more expressive than context-free languages.
Recursive language: Recursive languages are the type of formal languages that can be recognized by Turing machines. They are the most expressive type of formal language.
Non-context-free language: Non-context-free languages are the type of formal languages that cannot be recognized by pushdown automata. They are beyond the expressive power of context-free languages.
"In a context-free grammar, each production rule is of the form A → α, with A a single nonterminal symbol, and α a string of terminals and/or nonterminals (α can be empty)."
"This distinguishes it from a context-sensitive grammar, which can have production rules in the form αAβ → αγβ with A a nonterminal symbol and α, β, and γ strings of terminal and/or nonterminal symbols."
"A formal grammar is essentially a set of production rules that describe all possible strings in a given formal language."
"Production rules are simple replacements."
"There can be multiple replacement rules for a given nonterminal symbol."
"Nonterminal symbols are used during the derivation process but do not appear in its final result string."
"Languages generated by context-free grammars are known as context-free languages (CFL)."
"Different context-free grammars can generate the same context-free language."
"It is important to distinguish the properties of the language (intrinsic properties) from the properties of a particular grammar (extrinsic properties)."
"The language equality question (do two given context-free grammars generate the same language?) is undecidable."
"Context-free grammars arise in linguistics where they are used to describe the structure of sentences and words in a natural language."
"They were invented by the linguist Noam Chomsky for this purpose."
"In computer science, as the use of recursively-defined concepts increased, they were used more and more. In an early application, grammars are used to describe the structure of programming languages."
"In a newer application, they are used in an essential part of the Extensible Markup Language (XML) called the document type definition."
"Some authors use the term phrase structure grammar to refer to context-free grammars, whereby phrase-structure grammars are distinct from dependency grammars."
"A popular notation for context-free grammars is Backus–Naur form, or BNF."
"A formal grammar is essentially a set of production rules that describe all possible strings in a given formal language."
"Regardless of which symbols surround it, the single nonterminal A on the left-hand side can always be replaced by α on the right-hand side."
"The language generated by a grammar is the set of all strings of terminal symbols that can be derived, by repeated rule applications, from some particular nonterminal symbol ('start symbol')."