The goal is to construct a regular grammar for. This language is regular, as a regular expression can be constructed for it. The first language is, where the alphabet is. The left-linear grammar generates strings from the left to right, while the right-linear grammar generates strings starting at the last character. The left-linear grammars simply place the non-terminal before the terminal symbol in the body of the production, so. That is, the head of the production is a single non-terminal symbol, and the body consists of a single terminal symbol and at most one non-terminal symbol. In a right-linear grammar, the rules are of the form: or, where, , and. In particular, all rules must be either left-linear or right-linear. The regular grammar is a specific type of context-free grammar, where each regular grammar generates a regular language.ДЄ regular grammar is a context-free grammar in which all the production rules are linear. Recall that regular languages are a subset of context-free languages. This section will introduce the concept of a regular grammar. A single non-terminal is required, so, and the production rules simply deal with the cases mentioned above: The other case is when a pair of balanced parentheses are right next to each other. The first is similar to the example for, where parentheses can be nested. So what are the building blocks for this language? They are. Just like in the last example, it is important to start from the bottom up. We seek to build a grammar to generate this language. Now consider the language of balanced parentheses. So the grammar can be constructed with the single non-terminal symbol and the production rules: More generally, is constructed by nesting terms. Now using these building blocks, how is constructed? The only answer is to stick a in the middle of another, giving. As grammars define languages recursively, the goal is to build from the ground up. LetвЂ™s construct a context-free grammar to generate the language. The context-free grammar is generated starting at and following the productions until only terminals remain.Д¬onsider the example above with. The string on the right-hand side of the production symbol is known as the body. A production consists of a non-terminal symbol as the head, followed by the production symbol. Each production represents the recursive definition of the language. is the set of terminal symbols, which is equivocally the alphabet for the language.Note that non-terminals may reach other non-terminals. Each non-terminal symbol represents a set of strings- exactly those strings which can be reached by it. The pushdown automaton will be covered more thoroughly in a later blog entry.Д¬ontext-Free Grammar: A Context-Free Grammar is a four-tuple where: The context-free grammar will be formally introduced and examined. The term вЂњcontext-free grammarвЂќ is often times abused to denote the language itself.

These languages will be analyzed in greater detail later.ДЇormally, a context-free language is exactly the set of strings generated by a context-free grammar. Examples of strings with balanced parentheses include and, while is unbalanced. Some common examples of context-free languages are and the language of balanced parentheses. This is easy to see, as a pushdown automaton can accept a regular language simply by ignoring the stack.

Observe as well that all regular languages are context free. So now the computation machine has memory aside from the current state and character. Conceptually, a pushdown automaton starts with a finite state automaton then adds a stack. Context-Free Languages are those languages accepted by a machine called a pushdown automaton. This is perhaps the most intuitive way to introduce context-free languages. Recall from my previous blog entry on automata theory that the desired result is to formalize the notions of an algorithm and computation machines. Familiarity with regular languages and finite state automata is assumed.

Grammars are particularly useful in programming and markup language design. The recursive structure allows for effective parsing mechanisms. Grammars provide a recursive set of rules used to generate strings. This blog entry will introduce the notion of grammars to generate languages.

Grammar in finite state automata