Theory Of Computation PCCST302 KTU Semester 3 BTech 2024 Scheme

 Example: Grammar A 0 → a A 1 A_0 \to aA_1 ​ A 1 → b A 1   ∣   a   ∣   b A 0 A_1 \to bA_1 \ \mid\ a \ \mid\ bA_0 ​ We’ll use the standard construction: One NFA state per nonterminal ( A 0 , A 1 ) (A_0, A_1)   plus a fresh final state F F . For each rule X → a Y X \to aY : add a transition X → a Y X \xrightarrow{a} Y . For each rule X → a X \to a  (terminal only): add X → a F X \xrightarrow{a} F . Start state is the start nonterminal ( A 0 A_0 ​ ). Accepting states: { F } \{F\}  (no ε \varepsilon -rules here, so neither A 0 A_0 ​ nor A 1 A_1 ​ is accepting). NFA N = ( Q , Σ , δ , q 0 , F ) N = (Q,\Sigma,\delta,q_0,F) States Q = { A 0 , A 1 , F } Q = \{A_0, A_1, F\} Alphabet Σ = { a , b } \Sigma = \{a,b\} Start q 0 = A 0 q_0 = A_0 ​ Accepting F = { F } Transitions δ \delta : From A 0 A_0 : on a → { A 1 } \{A_1\}  (from A 0 → a A 1 A_0 \to aA_1 ​ ) on b → ∅ \varnothing From A 1 A_1 ​ ...

 Here’s the formal definition of a Context-Free Grammar (CFG). Definition A Context-Free Grammar is a 4-tuple: G = ( V , Σ , R , S ) G = (V, \Sigma, R, S) where: V V  — A finite set of nonterminal symbols (or variables). Σ \Sigma  — A finite set of terminal symbols , such that V ∩ Σ = ∅ V \cap \Sigma = \varnothing R R  — A finite set of production rules of the form A → α A \rightarrow \alpha where A ∈ V A \in V  and α ∈ ( V ∪ Σ ) ∗ \alpha \in (V \cup \Sigma)^*  (that is, α \alpha  is any finite string of terminals and/or nonterminals, possibly empty). S S  — A distinguished element of V V , called the start symbol . ✅ Key condition that makes it “context-free” : In every production A → α A \rightarrow \alpha , the left-hand side consists of exactly one nonterminal symbol A . Characteristics of CFGs Each production’s LHS must be a single nonterminal (unlike context-sensitive grammars). They can describe nested a...

  Regular Grammar A Regular Grammar is the most restricted type of grammar in the Chomsky Hierarchy . It generates exactly the class of regular languages (the same languages accepted by finite automata and described by regular expressions ). Formally, a grammar G = ( V , Σ , R , S ) G = (V, \Sigma, R, S)  is regular if all productions in R R  are of one of the following forms: Right-linear form : A → a B or A → a or A → ε A \rightarrow aB \quad \text{or} \quad A \rightarrow a \quad \text{or} \quad A \rightarrow \varepsilon where A , B ∈ V A, B \in V , a ∈ Σ a \in \Sigma . Left-linear form : A → B a or A → a or A → ε A \rightarrow Ba \quad \text{or} \quad A \rightarrow a \quad \text{or} \quad A \rightarrow \varepsilon Note: A grammar must be entirely right-linear or left-linear to be regular. Mixing both may lead to a CFG that is not regular. Intuition Regular grammars correspond to finite automata (DFA/NFA). Productions represent transitions ...

  What is a grammar (in automata)? A grammar is a formal tool  that generates strings of a language by repeatedly applying production rules . Formal definition A grammar is a 4-tuple G = ( V , Σ , R , S ) G=(V,\Sigma,R,S) : V V : finite set of nonterminals (variables) Σ \Sigma : finite set of terminals (alphabet), V ∩ Σ = ∅ V\cap\Sigma=\varnothing V ∩ Σ = ∅ R R : finite set of productions (rewrite rules) S ∈ V S\in V : start symbol Applying productions creates derivations (leftmost/rightmost), which can be shown by parse trees . The set of all terminal strings derivable from  S  is the language L ( G ) . Why grammars matter: They’re the generative counterpart to automata (the recognizers ). Each grammar class corresponds to a machine model: finite automata, pushdown automata, linear-bounded automata, Turing machines. The Chomsky hierarchy (types of grammars) Type-3: Regular Grammars (RG) Rule shape (choose one style consistently)...

Designing a Context-Free Grammar (CFG) is really about thinking recursively and breaking a language into smaller, replaceable parts. Here’s a step-by-step method explaining how to design CFGs. 1. Understand the Structure of the Language Identify patterns in the strings you want to generate. Look for recursion or nesting (these are strong hints that the language is context-free). Ask: “What must always match or balance?” Example 1: Balanced a ’s and b ’s: { a n b n   ∣   n ≥ 0 } \{ a^n b^n \ | \ n \ge 0 \} { a n b n   ∣   n ≥ 0 } Pattern: Same number of a ’s followed by same number of b ’s. Recursive idea: If aabb is in the language, then so is aa…bb with more pairs. 2. Choose Nonterminals for Main Components Start with S (start symbol). If the language has subparts, create separate variables for them. Example 2: Arithmetic expressions might need: V = { E , T , F } V = \{ E, T, F \} where E = expression, T = term, F = fa...