Select Page

Normal Forms of Context-Free Grammars (CFGs)

  1. Chomsky Normal Form (CNF):
    • In CNF, every production rule of the grammar is of the form:
      • A -> BC
      • A -> a
      • where A, B, and C are non-terminal symbols, and ‘a’ is a terminal symbol.
    • Additionally, the start symbol cannot appear on the right-hand side of any production rule except for the start symbol itself.
    • CNF grammars are particularly useful for parsing algorithms like the CYK algorithm due to their simplicity and regularity.
  2. Greibach Normal Form (GNF):
    • In GNF, every production rule is of the form:
      • A -> aα
    • where A is a non-terminal symbol, ‘a’ is a terminal symbol, and α is a possibly empty string of non-terminal symbols.
    • Unlike CNF, GNF allows for more flexibility in the structure of production rules, but it still imposes some restrictions to facilitate parsing.

Closure Properties of Context-Free Languages (CFLs)

Closure properties refer to the behavior of context-free languages under certain operations. For CFLs, the closure properties include:

  1. Union: If L1 and L2 are CFLs, then their union L1 ∪ L2 is also a CFL. This means that CFLs are closed under the union operation.
  2. Concatenation: If L1 and L2 are CFLs, then their concatenation L1 ∘ L2 is also a CFL. CFLs are closed under concatenation.
  3. Kleene Star: If L is a CFL, then its Kleene star L* is also a CFL. CFLs are closed under the Kleene star operation.
  4. Intersection: CFLs are not closed under intersection. In other words, if L1 and L2 are CFLs, their intersection may not necessarily be a CFL.
  5. Complementation: CFLs are not closed under complementation. Given a CFL L, its complement may not be a CFL.
  6. Homomorphism: If L is a CFL and h is a homomorphism, then h(L) is also a CFL.
  7. Inverse Homomorphism: If L is a CFL and h is a homomorphism, then h^(-1)(L) is also a CFL.

Understanding these closure properties is important for understanding the behavior of context-free languages under various operations and transformations, which is crucial in formal language theory and compiler construction.