PENGERTIAN BENTUK NORMAL CHOMSKY DAN ALGORITMA CYK UNTUK TATA BAHASA BEBAS KONTEKS

Summary

This presentation explains the concept of Chomsky Normal Form (CNF) in context-free grammar (CFG). It covers the definition of CNF, its applications in simplifying context-free grammars, and the steps to convert CFG into CNF. Key topics include eliminating useless productions, unit productions, and epsilon rules. The script also introduces the CK algorithm, used to check membership in a CFG and determine if a string can be derived. Several examples are given to illustrate these transformations, emphasizing the importance of CNF in simplifying grammar rules for computational purposes.

Takeaways

• 😀 Chomsky Normal Form (CNF) is an essential normal form used for context-free grammars (CFG).
• 😀 A CFG can be transformed into CNF through simplification, such as removing useless productions and unit productions.
• 😀 CNF production rules consist of either two variables or a terminal symbol on the right-hand side.
• 😀 The process of transforming CFG to CNF involves replacing productions with terminal symbols or two-variable productions.
• 😀 The CK algorithm is a version of the CYK algorithm designed to check if a string can be generated from a CFG in CNF.
• 😀 CNF can be formed by applying production rule simplifications repeatedly until the CFG adheres to the CNF structure.
• 😀 A CFG in CNF ensures that each production either produces a terminal symbol or a combination of two variables.
• 😀 The CK algorithm is useful for testing membership in CFGs that are already in CNF.
• 😀 The steps for transforming a CFG into CNF include eliminating non-terminal symbols that do not contribute to derivations and replacing certain kinds of productions with appropriate ones.
• 😀 An example of a CFG transformation to CNF involves creating new variables to replace terminal symbols in complex productions.

Q & A

What is Chomsky Normal Form (CNF)?

Chomsky Normal Form (CNF) is a specific form of context-free grammar (CFG) where every production rule is either of the form 'A → BC' (two variables) or 'A → a' (a terminal). It is particularly useful for simplifying context-free grammars and making them easier to process by parsers.

What are the basic characteristics of a grammar in CNF?

A grammar is in Chomsky Normal Form if every production is either a terminal (e.g., A → a) or has two variables (e.g., A → BC). This simplification ensures that there are no useless variables or units in the grammar, making it more efficient for parsing algorithms.

Why is Chomsky Normal Form important in formal language theory?

Chomsky Normal Form is important because it allows for simpler, more efficient parsing of context-free languages. It standardizes the structure of the grammar, which is especially beneficial for algorithms like the CYK (Cocke-Younger-Kasami) algorithm, which is used to determine if a string can be generated by a grammar.

What is the general process for converting a CFG to CNF?

To convert a context-free grammar (CFG) to CNF, follow these steps: 1) Remove useless symbols, 2) Eliminate unit productions (productions where a non-terminal produces another single non-terminal), 3) Simplify productions that don't conform to CNF by introducing new variables to ensure all rules are either in the form A → BC or A → a.

Can you give an example of a production rule that violates CNF?

A production rule like 'A → BcD' violates CNF because it has more than two variables on the right-hand side. In CNF, the right-hand side must consist of either two variables or a single terminal.

What is the CK algorithm, and how is it used in CNF?

The CK algorithm, or CYK (Cocke-Younger-Kasami) algorithm, is a parsing algorithm that is used to determine if a given string can be derived from a context-free grammar in Chomsky Normal Form. It works by constructing a table to check if a string can be generated from the grammar's production rules.

What are the conditions for using the CYK algorithm?

The CYK algorithm can only be applied to context-free grammars that are already in Chomsky Normal Form. It works by checking whether a string can be derived using the grammar's production rules in a dynamic programming approach.

What is the role of terminal and variable symbols in CNF?

In CNF, terminal symbols (denoted as lowercase letters) represent the basic units of the language, while variables (denoted as uppercase letters) are used to represent non-terminal symbols that can be expanded further through production rules. Each production in CNF must conform to specific forms involving terminals or two variables.

What does it mean for a production to be 'useless' in the context of CFG and CNF?

A 'useless' production is one where a non-terminal symbol cannot contribute to the derivation of a terminal string or is unreachable from the start symbol. In CNF conversion, such productions are removed to simplify the grammar.

How do you handle productions that contain more than two variables during the conversion to CNF?

When a production contains more than two variables, we introduce new non-terminal variables to break the production down into binary rules that conform to the CNF form. For example, a production like A → BCD would be transformed by introducing an intermediate variable to create rules like A → BE and E → CD.