Questions and Answers
What are the two types of derivation used to find whether a string belongs to a given grammar?
Leftmost derivation and Rightmost derivation
What is the characteristic of an ambiguous grammar?
For every S in the language, aSb is ______.
in L
Define ambiguous grammar.
Signup and view all the answers
Is the grammar 'S -> aS | Sa | 𝜖' ambiguous?
Signup and view all the answers
Which form of the grammar helps eliminate the ambiguity?
Signup and view all the answers
In CNF, every production is of the form A -> BC or A -> a. (Fill in the blanks)
Signup and view all the answers
What is the Chomsky hierarchy used for?
Signup and view all the answers
What type of grammar is also known as Phrase Structure Grammar?
Signup and view all the answers
Context Sensitive Grammar can have strings that are empty.
Signup and view all the answers
Type 2 grammars are also known as ____________.
Signup and view all the answers
Match the type of grammar with its corresponding form of production:
Signup and view all the answers
Write the CFG for the language consisting of any strings of 'a' and 'b'.
Signup and view all the answers
Provide the CFG for generating strings that start and end with the same symbol from '0' and '1'.
Signup and view all the answers
Create a CFG for the language of even and odd-length palindrome strings over the alphabet {a, b}.
Signup and view all the answers
Write the CFG for regular expression (a+b)*a(a+b)a(a+b).
Signup and view all the answers
Write a CFG for the language where the number of 0's is equal to the number of 1's.
Signup and view all the answers
Define the set Vc.
Signup and view all the answers
What are the first two steps in deriving x in Gc?
Signup and view all the answers
In the context of Kleene (), what does L1 contain?
Signup and view all the answers
How is the language L1* generated?
Signup and view all the answers
What is the final step in converting a Context-Free Grammar (CFG) to Chomsky Normal Form (CNF)?
Signup and view all the answers
Which step is not required in the process of converting a CFG to CNF if there are no epsilon (^) productions?
Signup and view all the answers
In the Union operation for Context-Free Grammars, if L1 and L2 are context-free languages, the language L1 U L2 will also be a context-free language.
Signup and view all the answers
In the Concatenation operation for Context-Free Grammars, a grammar Gc generating L1L2 is denoted by Gc= (Vc, Ʃ, Sc, ___).
Signup and view all the answers
Match the following components of the CFG conversion process to their respective descriptions:
Signup and view all the answers
Study Notes
Theory of Computation
Unit 3: Context Free Grammar
Chomsky Hierarchy
- Classification of grammar:
- Unrestricted grammar (type 0)
- Context sensitive grammar (type 1)
- Context free grammar (type 2)
- Regular grammar (type 3)
Type 0 Grammar (Phrase Structure Grammar)
- Productions are of the form: α → β, where α and β can be strings of terminal and non-terminal symbols.
- Example: S → ACaB, Bc → acB, CB → DB, aD → Db
Type 1 Grammar (Context Sensitive Grammar)
- Productions are of the form: αAβ → αγβ, where A is non-terminal, and α, β, and γ are strings of terminals and non-terminals.
- Example: AB → AbBc, A → bcA, B → b
Type 2 Grammar (Context Free Grammar)
- Productions are of the form: A → α, where A is non-terminal, and α is a string of terminals and non-terminals.
- Example: S → Xa, X → a, X → aX, X → abc
Type 3 Grammar (Linear or Regular Grammar)
- Productions are of the form: A → a or A → aB, where A and B are non-terminals, and a is a terminal.
- Example: X → a | aY, Y → b
Hierarchy of Grammar
- Type 3 (Regular) is a subset of Type 2 (Context Free), which is a subset of Type 1 (Context Sensitive), which is a subset of Type 0 (Unrestricted)
Context Free Grammar
- A context free grammar (CFG) is a 4-tuple: G = (V, Σ, S, P)
- V is a finite set of non-terminals
- Σ is a disjoint finite set of terminals
- S is an element of V and is the start symbol
- P is a finite set of productions of the form: A → α, where A is non-terminal and α is a string of terminals and non-terminals
Context Free Language
- A language is a context free language (CFL) if there is a CFG that generates it.
CFG Examples
- Write CFG for:
- either a or b: S → a | b
- a+: S → aS | a
- a*: S → aS | ^
- (ab)*: S → abS | ^
- any string of a and b: S → aS | bS | a | b
- Write CFG for:
- ab*: S → aX, X → ^ | bX
- ab: S → XY, X → aX | ^, Y → bY | ^
- (a+b)*: S → aS | bS | ^
- a(a+b)*: S → aX, X → aX | bX | ^
- Write CFG for:
- a* | b*: S → A | B, A → ^ | aA, B → ^ | bB
- (011+1)(01): S → AB, A → 011A | 1A | ^, B → 01B | ^
- balanced parenthesis: S → [] | {} | [S] | {S} | ^
- Write CFG for:
- at least three times: S → A1A1A1A, A → 0A | 1A | ^
- must start and end with same symbol: S → 0A0 | 1A1, A → 0A | 1A | ^
- language of even & odd length palindrome string over {a,b}: S → aSa | bSb | a | b | ^
- no. of a and no. of b are same: S → aSb | bSa | ^
- Write CFG for:
- regular expression (a+b)*a(a+b)a(a+b): S → XaXaX, X → aX | bX | ^
- number of 0's and 1's are same: S → 0S1 | 1S0 | ^
- L={aibjck | i=j or j=k}: S → AB, A → aAb | ab, B → cB | c, or S → CD, C → aC | a, D → bDc | bc
Recursive Definitions
- Example: CFG for {a,b}*: S → aS | bS | ^
- Recursive definition of a language L: S ∈ L, aS ∈ L, bS ∈ L, and no other strings are in L.### Recursive Definition of Palindrome
- A CFG (Context-Free Grammar) is defined as S → aSa | bSb | a | b, where Σ = {a, b} and L = {aSa, bSb, a, b}.
- Any string S in L can be generated as aSa or bSb, and no other strings are in L.
Recursive Definition of a Language
- A CFG is defined as S → b, and for any string S in L, aSb is in L.
- The language L consists of all strings of the form b, where n ≥ 0.
FA to Regular Grammar
- A FA (Finite Automaton) can be converted to a regular grammar.
- The grammar rules are derived from the transitions of the FA.
Derivation
- A derivation is a way to find whether a string belongs to a given grammar or not.
- There are two types of derivation: leftmost derivation and rightmost derivation.
Leftmost Derivation
- A leftmost derivation is a derivation where at every step, the leftmost non-terminal is replaced.
- The parse tree represents the structure of the derivation.
Rightmost Derivation
- A rightmost derivation is a derivation where at every step, the rightmost non-terminal is replaced.
- It is also called canonical derivation.
Ambiguous Grammar
- An ambiguous grammar is a grammar that produces more than one leftmost or rightmost derivation for the same sentence.
- Example: S → S+S | SS | (S) | a, output string: a+aa.
Unambiguous Grammar
- An equivalent unambiguous grammar is a grammar that produces only one leftmost or rightmost derivation for the same sentence.
- Example: S → S+T | T, T → TF | F, F → (S) | a, output string: a+aa.
Simplified Forms and Normal Forms
- Simplified forms and normal forms of a grammar are used to simplify the grammar and remove unnecessary productions.
Nullable Variable
- A nullable variable in a CFG is a variable that can be derived to the empty string.
- A variable is nullable if it is possible to derive the empty string from it.
Eliminate ˄ Production
- A production of the form A → ˄ can be eliminated by replacing A with ˄ in all productions containing A on the RHS.
A-Derivable
- A variable is A-derivable if it can be derived from A using a sequence of productions.
- A variable is A-derivable if it can be derived from A using a sequence of productions, and the production is of the form A → B.### Unit Production & Elimination of Unit productions
- A production of the form A→B is termed as unit production, where A and B are non-terminals.
- Algorithm to eliminate unit productions:
- Initialize P1 to be P.
- For each A ∈ V, find the set of A-derivable variables.
- For every pair (A, B) such that B is A-derivable and every non-unit production B→α, add the production A→α to P1 if it is not already present in P1.
Elimination of Unit Productions
- Example: Eliminate unit productions from the given CFG: S→ABA|BA|AA|AB|A|B, A→aA|a, B→bB|b
- Steps:
- Remove unit productions S→A and S→B
- Resulting CFG: S→ABA|BA|AA|aA|a|bB|b, A→aA|a, B→bB|b
CFG to CNF (Chomsky Normal Form)
- A CFG is in CNF if every production is one of the two forms:
- A→a, where A is a non-terminal and a is a terminal
- A→BC, where A, B, and C are non-terminals
- Steps to convert CFG to CNF:
- Eliminate ʌ-productions
- Eliminate unit productions
- Restrict the right side of productions to single terminal or string of two or more non-terminals
- Final step of CNF: shorten the string of NT to length 2
Examples of CFG to CNF
- Example 1: Convert CFG to CNF: S→AAC, A→aAb|ʌ, C→aC|a
- Steps:
- Eliminate ʌ-production: A→aAb|ab
- Eliminate unit productions: S→AAC|AC|aC, A→aAb|ab, C→aC|a
- Resulting CNF: S→AX1, X1→AC, A→PQ, Q→AQ, C→PC, P→a, Q→b
- Example 2: Convert CFG to CNF: S→aAbB, A→Ab|b, B→Ba|a
- Steps:
- Eliminate unit productions: S→aAbB, A→Ab|b, B→Ba|a
- Resulting CNF: S→PT1, T1→AT2, T2→QB, A→AQ|b, B→BP|a, P→a, Q→b
Backus-Naur Form (BNF)
- BNF is a notation technique for context-free grammar.
- It is often used to describe the syntax of a language used in computing.
- Variables written between < > are non-terminals.
- Vertical bar ‘|’ indicates an alternate choice.
- […] is used to enclose an optional specification.
Union, Concatenation, and Kleene's of CFG
- Theorem: If L1 and L2 are context-free languages, then the languages L1 U L2, L1L2, and L1* are also CFLs.
- Constructive proof: Starting with CFGs G1 = (V1, Σ, S1, P1) and G2 = (V2, Σ, S2, P2) generating L1 and L2, respectively, we show how to construct a new CFG for each of the three cases:
- Gu = (Vu, Σ, Su, Pu) generating L1 U L2
- Gc = (Vc, Σ, Sc, Pc) generating L1L2
- G* = (V, Σ, S, P) generating L1*
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Description
This quiz covers the fundamentals of Context Free Grammar in the Theory of Computation, specifically in Unit-3. Test your understanding of the concepts taught by Prof. Dixita B.Kagathara.
