ITEC 420 - Chapter 2 - Context Free Languages

Section 2.1 - Context Free Grammars

Chapter 2 - Overview

Grammars Generate/Derive Strings

Generating Strings - Derivations

Defining a Grammar

Example Grammar

Example Derivation

Another Example Grammar

Example Grammar with ε

Common Practice in Grammar Definitions

Parse Tree

Context Free Grammar: Definition

Context Free Language: Definition

Non Context Free Grammar

Some Grammar Shorthands

Some Example Languages

CFL for Regular Languages

Expression Grammar

Other Tips on Defining CFL

CFG Terminology: yields, derives, language of a grammar

Leftmost and Rightmost Derivations

Leftmost Derivations and Ambiguity

Inherent Ambiguity

Chomsky Normal Form (CNF)

Chomsky Normal Form - Example

Chomsky Normal Form - Motivation

Conversion to CNF

Conversion to CNF - Examples

Some Undecidable Problems for CFL and CFG