Theory Of Computation PCCST302 KTU Semester 3 BTech 2024 Scheme

Ambiguity in grammars is a very important concept in Context-Free Grammars (CFGs) , especially because it directly affects parsing, compiler design, and language clarity .  🔹 What is Ambiguity in a Grammar? A context-free grammar (CFG) is said to be ambiguous if at least one string in the language it generates has more than one distinct parse tree (or equivalently, more than one leftmost or rightmost derivation). 👉 Formally: A CFG G G  is ambiguous if ∃    w ∈ L ( G ) such that w       has two or more different parse trees. \exists \; w \in L(G) \quad \text{such that} \quad w \;\; \text{has two or more different parse trees.} 🔹 Why is Ambiguity a Problem? In programming languages , ambiguity makes parsing uncertain : Example: Does a + b * c mean (a + b) * c or a + (b * c) ? Compilers require deterministic parsing → ambiguous grammars must be avoided or rewritten. 🔹 Example of an Ambiguous Grammar Consider the C...

  🔹 What Does Resolving Ambiguity Mean? A CFG is ambiguous if some string has more than one parse tree. To resolve ambiguity , we rewrite the grammar so that every valid string has exactly one parse tree (i.e., unambiguous grammar). 🔹 Methods to Resolve Ambiguity ✅ (a) Enforce Operator Precedence Ensure * is evaluated before + . Example: Ambiguous grammar: E → E + E    ∣    E ∗ E    ∣    ( E )    ∣    a E \to E + E \;|\; E * E \;|\; (E) \;|\; a Unambiguous grammar (with precedence): E → E + T    ∣    T E \to E + T \;|\; T T → T ∗ F    ∣    F T \to T * F \;|\; F F → ( E )    ∣    a F \to (E) \;|\; a Now in a + a * a , multiplication ( * ) happens before addition ( + ). So only one parse tree is possible. ✅ (b) Enforce Operator Associativity Ambiguity also arises in expressions like a - b - c . Should it be (a - b) - c (left-associative) or a - (b - c) (right-associative)? We rewrite grammar for left-associativity : E → E − T    ∣    T E \to E - ...

  1. What are “useless symbols”? A useless symbol in a CFG is a non-terminal or terminal that does not contribute to deriving any string of terminals from the start symbol . There are  two types of useless symbols : Non-generating symbols Symbols that cannot derive any terminal string . Example: If a non-terminal never leads to terminals, it is useless. Non-reachable symbols Symbols that cannot be reached from the start symbol . Even if they could generate terminals, if the start symbol never reaches them, they are useless. We remove both types to simplify the grammar. 2. Step 1: Remove Non-Generating Symbols Algorithm : Mark all terminal symbols as generating. Iteratively mark non-terminals A as generating if there exists a production: A → α A \rightarrow \alpha where every symbol in α is already generating . Repeat until no new generating symbols are found. Remove all non-generating symbols and any production containing them. ...

  🔹 Definition  A context-free grammar is said to be in Greibach Normal Form (GNF) if all productions have the form: A    →    a X 1 X 2 ⋯ X k A \;\to\; aX_1X_2 \cdots X_k ​ where A ∈ V A \in V  (a nonterminal), a ∈ T a \in T  (a terminal), each X i ∈ V X_i \in V , and k ≥ 0. That means: every production starts with a terminal, followed optionally by nonterminals . 🔹 Comparison with other normal forms Chomsky Normal Form (CNF): Right-hand side is either two variables ( A → B C A \to BC ) or a single terminal ( A → a A \to a ). Greibach Normal Form (GNF): Right-hand side must begin with a terminal , then zero or more variables. 👉 So CNF is binary-variable structured , while GNF is terminal-first structured . 🔹 Why GNF is important (speciality) Every context-free language (without λ) has an equivalent grammar in GNF. Useful in top-down parsing because the derivation always produces a terminal as the next symbol. No left r...

  🔹 Why CFGs in Programming Languages? Programming languages (like C, Java, Python) have complex syntax : Nested structures: if … then … else … Balanced symbols: { } , ( ) , [ ] Expressions with operator precedence and associativity Loops, function calls, recursive definitions 👉 Regular grammars (or finite automata) are not powerful enough to handle such constructs. CFGs are powerful enough because they naturally describe hierarchical and nested structures . 🔹  CFG as the Basis of Syntax A Context-Free Grammar formally defines the syntax rules of a programming language. Example (simplified arithmetic grammar): E → E + T ∣ T E \to E + T \mid T T → T ∗ F ∣ F T \to T * F \mid F F → ( E ) ∣ id F \to (E) \mid \text{id} This grammar: Defines valid arithmetic expressions. Enforces precedence ( * before + ) and associativity (left-to-right). ✅ So, id + id * id is valid. ❌ But + * id id is not. 🔹 Role in Compiler Design Compilers use CFGs i...

  🌿 Context-Sensitive Grammar (CSG) Definition A context-sensitive grammar (CSG) is a formal grammar G = ( V , Σ , R , S ) where every production (rule) in R R R is of the form: α A β → α γ β \alpha A \beta \rightarrow \alpha \gamma \beta such that A ∈ V − Σ A \in V - \Sigma , α , β ∈ ( V ∪ Σ ) ∗ \alpha, \beta \in (V \cup \Sigma)^* , and γ ∈ ( V ∪ Σ ) +. That means: The nonterminal A can be replaced by γ , But only in the context of α (on the left) and β (on the right). Also, the length of the right-hand side is at least the length of the left-hand side: ∣ α A β ∣ ≤ ∣ α γ β ∣ |\alpha A \beta| \leq |\alpha \gamma \beta| — so no production makes the string shorter. This non-decreasing length property makes them context-sensitive . Intuitive Meaning The replacement (rewriting) of a symbol depends on its context in the string. Hence the name “context-sensitive.” The grammar cannot “shrink” a string (unlike context-free grammars). Language T...

  📘 Chomsky Normal Form (CNF) ✅ Definition A context-free grammar (CFG) is said to be in Chomsky Normal Form if every production rule is of the form: Two nonterminals : A    →    B C A \;\to\; BC where A , B , C A, B, C are variables (nonterminals) and neither B B  nor C C  is the start symbol. Single terminal : A    →    a A \;\to\; a where a a  is a terminal symbol. Optional ε-production (only if the language includes ε): S    →    ε S \;\to\; \varepsilon allowed only if S S  is the start symbol and S S  does not appear on the right-hand side of any rule. ❌ What is NOT allowed Rules like A → ε  (except possibly for start symbol). Rules like A → B  (unit productions). Rules like A → a B  (mix of terminal + nonterminal). Rules with more than 2 nonterminals on the RHS (e.g., A → B C D ). Rules with more than 1 terminal on the RHS (e.g., A → a b ). 🌟 Example 1: Grammar in CNF A→ A B ∣ BC A → B A ∣ a B ...