Automata Theory Questions
A context-free grammar is a formal grammar that consists of a set of production rules used to generate strings in a formal language. It is called "context-free" because the left-hand side of each production rule only contains a single non-terminal symbol, and the right-hand side can contain a combination of non-terminal and terminal symbols.
In a context-free grammar, each non-terminal symbol represents a different type of phrase or syntactic structure, while the terminal symbols represent the actual words or symbols in the language. The production rules define how these non-terminal symbols can be replaced by a sequence of terminal and non-terminal symbols.
Context-free grammars are widely used in computer science and linguistics to describe the syntax of programming languages and natural languages. They are often represented using a notation called Backus-Naur Form (BNF) or Extended Backus-Naur Form (EBNF).