CSE322 Normal Forms: CNF & GNF
22 Questions
0 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to Lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

What is the name of the first step to convert a CFL grammar to CNF?

Arrange that all bodies of length 2 or more to consist only of variables.

What is the goal of the second step to convert a CFL grammar to Chomsky Normal Form (CNF)?

Break bodies of length 3 or more into a cascade of productions, each with a body consisting of two variables.

What are the three preliminary simplifications for converting a context-free grammar to Chomsky Normal Form (CNF)?

  • Reduce useless productions, Reduce epsilon productions, Reduce unit productions
  • Eliminate empty productions, Eliminate unit productions, Eliminate useless symbols (correct)
  • Eliminate useless symbols, Eliminate ε productions, Eliminate unit productions (correct)
  • Eliminate ε productions, Eliminate unit productions, Eliminate Useless Symbols
  • Remove useless symbols, Remove ε-productions, Remove unit productions

In the context of a grammar, unit productions are essential for generating the language.

<p>False (B)</p> Signup and view all the answers

A grammar is considered to be in Chomsky Normal Form (CNF) if all productions are in the form A -> BC or A -> a, where A, B, and C are non-terminal symbols, and a is a terminal symbol.

<p>True (A)</p> Signup and view all the answers

Describe the concept of 'generating' a symbol in the context of eliminating useless symbols.

<p>A symbol X is generating if it can derive a terminal string w.</p> Signup and view all the answers

Explain the concept of 'reachable' symbol in the context of eliminating useless symbols.

<p>A symbol X is reachable if there is a derivation that starts with the start symbol and ends with a string containing X.</p> Signup and view all the answers

What is the difference between generating and reachable symbols?

<p>A generating symbol can produce a terminal string, while a reachable symbol can be derived from the start symbol.</p> Signup and view all the answers

The order in which useless symbols are removed (first non-reachable, then non-generating) is crucial and cannot be reversed.

<p>True (A)</p> Signup and view all the answers

A grammar is in Chomsky Normal Form if it has no unit productions.

<p>False (B)</p> Signup and view all the answers

What is a unit production?

<p>A unit production is a production of the form A → B, where both A and B are non-terminal symbols.</p> Signup and view all the answers

What are the final steps involved in converting a CFL grammar to Chomsky Normal Form (CNF)?

<p>The final steps involve ensuring that all bodies of length 2 or more consist only of variables and then breaking down bodies of length 3 or more into a cascade of productions, each with a body consisting of two variables.</p> Signup and view all the answers

A grammar in Chomsky Normal Form (CNF) has productions only in the format A → BC or A → a.

<p>True (A)</p> Signup and view all the answers

What is the central idea behind converting a CFL grammar to Chomsky Normal Form (CNF)?

<p>The central idea is to ensure that all productions in the grammar have at most two symbols in their body, either two non-terminals or a single terminal.</p> Signup and view all the answers

A context-free grammar is in Greibach Normal Form (GNF) if all productions are in the form A → aX, where A is a non-terminal symbol, a is a terminal symbol, and X is a sequence of (possibly empty) non-terminal symbols.

<p>True (A)</p> Signup and view all the answers

What is the key difference in format between Chomsky Normal Form (CNF) and Greibach Normal Form (GNF)?

<p>In CNF, each production has at most two symbols in its body, while in GNF, the body must start with a single terminal symbol, followed by a (possibly empty) string of non-terminals.</p> Signup and view all the answers

The Chomsky Normal Form (CNF) can be used as a starting point for the CYK parsing algorithm.

<p>True (A)</p> Signup and view all the answers

What is a derivation tree in the context of parsing a grammar?

<p>A derivation tree represents the steps of parsing a string, showing how the start symbol is transformed into the target string through a series of productions.</p> Signup and view all the answers

A derivation tree in a Chomsky Normal Form (CNF) grammar is a binary tree.

<p>True (A)</p> Signup and view all the answers

Any string of length 'n' in a grammar in Greibach Normal Form (GNF) can be derived in exactly 'n' steps.

<p>True (A)</p> Signup and view all the answers

Grammars in normal form (CNF or GNF) can facilitate the process of proving properties related to languages generated by the grammar.

<p>True (A)</p> Signup and view all the answers

The Chomsky Normal Form (CNF) removes all the productions in a grammar that have ε symbols in their body.

<p>True (A)</p> Signup and view all the answers

Flashcards

String

A sequence of characters, often used to represent text or code.

Grammar

A formal system that defines the syntax of a language.

Context-free grammar (CFG)

A grammar is context-free if the left-hand side of each production rule consists of a single non-terminal symbol.

Nullable variable

A non-terminal symbol that can derive the empty string (ε).

Signup and view all the flashcards

Unit production

A production rule of the form A → B, where both A and B are non-terminal symbols.

Signup and view all the flashcards

Chomsky Normal Form (CNF)

A grammar where the productions are of the form A → BC or A → α, where A, B, and C are non-terminal symbols, and α is a terminal symbol.

Signup and view all the flashcards

Greibach Normal Form (GNF)

A grammar where the productions are of the form A → αX, where A is a non-terminal symbol, α is a terminal symbol, and X is a sequence of (possibly empty) non-terminal symbols.

Signup and view all the flashcards

Reachable symbol

A non-terminal symbol that can be derived from the start symbol. It can be reached in the derivation.

Signup and view all the flashcards

Generating symbol

A non-terminal symbol that can derive a string of terminal symbols. It can produce actual text.

Signup and view all the flashcards

Useful symbol

A symbol that is both reachable and generating.

Signup and view all the flashcards

Eliminate non-generating symbols

A process of removing non-generating symbols from a grammar.

Signup and view all the flashcards

Eliminate non-reachable symbols

A process of removing non-reachable symbols from a grammar.

Signup and view all the flashcards

Eliminate ε productions

A process of eliminating production rules that contain the empty string (ε) as the right-hand side.

Signup and view all the flashcards

Start symbol standardization

A process of transforming grammar rules to ensure that only the designated start symbol can produce a string of terminal symbols.

Signup and view all the flashcards

Terminal symbol standardization

A process of transforming grammar rules to ensure that all terminal symbols appear only in the right-hand side of production rules.

Signup and view all the flashcards

Eliminate unit productions

A process of removing production rules of the form A→B where both A and B are non-terminal symbols.

Signup and view all the flashcards

Body decomposition

Creating new non-terminal symbols and production rules to break down longer production bodies.

Signup and view all the flashcards

Terminal extraction

Replacing terminal symbols within long production bodies with new non-terminal symbols that have single production rules producing the original terminal.

Signup and view all the flashcards

Eliminate left-recursion

A process of removing left-recursive productions from a grammar.

Signup and view all the flashcards

Derivation

A notation used to describe the process of deriving strings in a formal language using a grammar.

Signup and view all the flashcards

Derivation tree

A tree-like structure that represents the derivation of a string in a formal language.

Signup and view all the flashcards

Formal language theory

A branch of computer science that deals with formal systems for describing and analyzing languages.

Signup and view all the flashcards

Conversion to Chomsky Normal Form

A process of converting a context-free grammar into an equivalent grammar in Chomsky Normal Form.

Signup and view all the flashcards

Conversion to Greibach Normal Form

A process of converting a context-free grammar into an equivalent grammar in Greibach Normal Form.

Signup and view all the flashcards

Rule combination

The process of combining multiple production rules for a particular non-terminal symbol into a single rule.

Signup and view all the flashcards

Grammar optimization

A process of optimizing a grammar by removing redundant rules or symbols.

Signup and view all the flashcards

Grammar verification

A process of testing a grammar for correctness and completeness.

Signup and view all the flashcards

Grammar rules

A set of production rules that define the structure of a formal language.

Signup and view all the flashcards

Study Notes

CSE322 Normal Forms: CNF & GNF

  • The lecture covers Chomsky Normal Form (CNF) and Greibach Normal Form (GNF) for context-free grammars.
  • A presentation outline includes introduction, Chomsky normal form, preliminary simplifications, final steps, Greibach Normal Form, algorithm example, and summary.
  • A grammar is defined as G = (V, T, P, S), where:
    • V is a set of variables.
    • T is a set of terminals.
    • P is a set of productions.
    • S is the start symbol.
  • An example grammar is provided, with terminals T = {a, b}, variables V = {A, B, C}, start symbol S, and production P = S → A.
  • A grammar example illustrates how a grammar generates strings, such as L = {anbncn | n ≥ 1}.
  • Context-free grammar: the head of any production contains only one non-terminal symbol. -Example S→P; P→aPb; P→ε; L = {anbn | n ≥ 0}
  • Chomsky Normal Form: all productions are either A → BC or A → a, where A, B, and C are non-terminal symbols and a is a terminal symbol.
  • Preliminary simplifications for CNF include eliminating useless symbols, ε productions, and unit productions.
  • Useless symbols are identified by generating and reachable symbols. A symbol is generating if it can derive a terminal string. A symbol is reachable if it can be derived from the start symbol.
  • ε productions are productions that produce the empty string.
    • Create two versions of the production, one with the nullable variable and one without.
    • Eliminate productions with empty bodies.
  • Unit productions are productions of the form A → B where A and B are variables.
    • Identify unit pairs
    • Replace every occurrence of B with ω.
  • Steps to convert a grammar to CNF:
    • Arrange all bodies of length 2 or more to consist only of variables.
    • Break bodies of length 3 or more into a cascade of productions, each with a body consisting of two variables.
  • Greibach Normal Form: all productions are of the form A → aX, where A is a non-terminal symbol, a is a terminal symbol, and X is a sequence of non-terminal symbols (possibly empty).
  • Example of removing non-generating and non-reachable symbols are given.
  • Steps for finding generating and reachable symbols.
  • Examples for ε productions and unit productions are shown.
  • Summary of the properties of CNF and GNF, including how derivation trees are structured, how string lengths relate to derivation steps, and how normal forms facilitate proofs.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Quiz Team

Related Documents

CSE322 Normal Forms: CNF & GNF Lecture Notes PDF

Description

This quiz covers Chomsky Normal Form (CNF) and Greibach Normal Form (GNF) as they apply to context-free grammars. It includes explanations of grammar definitions, production examples, and the rules governing normal forms. Test your understanding of these crucial concepts in formal language theory.

More Like This

Chomsky's Theory of Universal Grammar
3 questions

Chomsky's Theory of Universal Grammar

GiftedButtercup avatar
GiftedButtercup
Chomsky's Language Acquisition Model
57 questions

Chomsky's Language Acquisition Model

BrightestBoston2440 avatar
BrightestBoston2440
SOC 102 - Chomsky and Sports
35 questions

SOC 102 - Chomsky and Sports

CompliantMemphis avatar
CompliantMemphis
Chomsky, Skinner and the Cognitive Revolution
33 questions

Chomsky, Skinner and the Cognitive Revolution

ImpressedRuby avatar
ImpressedRuby
Use Quizgecko on...
Browser
Open
Browser
Browser