DOC PREVIEW
MIT 16 070 - Recitation 11 Notes

This preview shows page 1-2 out of 6 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Recitation 11 Notes Context Free Grammars Definition: A grammar G = (V, T, P,S) is a context free grammar (cfg) if all productions in P have the form A →x where • A ∈V, and • x ∈ (V ∪T)*. Examples Problem 1. Given the language L = {anbn: n ≥0}, what is the CFG that generates the language? G = ({S}, {a, b}, {S→aSb, S→ε}, S} Problem 2. Given the language L = {anbk: k > n ≥0}, what is the CFG that generates the language? G = ({S, B}, {a, b}, {S→aSb, S→B, B→bB, B→b}, S). Problem 3. The language L = {w: w ∈{a, b}*, na(w) = nb(w)}, what is the CFG that defines the language? G = ({S}, {a, b}, {S→aSb, S→bSa, S→SS, S→ε},S). What is the PDA that recognizes this language? 1. Get input symbol 2. If input symbol is an ‘a’ o If the stack is empty or stack_top = ‘A’, push stack symbol ‘A’ on the stack Go to Step 1. o If stack_Top = ‘B’ Pop it from the stack Go to Step 1. 3. If input symbol is a ‘b’ o If the stack is empty or stack_top = ‘B’, push stack symbol ‘B’ on the stackGo to Step 1. o If the stack_top = ‘A’ Pop it from the stack Go to Step 1. 4. If there are no more input symbols, o If stack is empty, then accept o Else Reject. Problem 4. The language L consists of a balanced set of parentheses. Write a CFG that generates the language. G = ({S}, {, }, {S→S, S→SS, S→ε}, S). Definition: A sentential form is the start symbol S of a grammar or any string in (V ∪T)* that can be derived from S. Consider the grammar G = ({S, A, B, C}, {a, b, c}, P, S) where P = {S→ABC, A→aA, A→ε, B→bB, B→ε, C→cC, C→ε}. Derivation 1: S ABC aABC aABcC aBcC abBcC abBc abbBcabbc Definition: In a leftmost derivation, the leftmost variable is always expanded first: S ABCaABCaBCabBC abbBC abbC abbcC abbc Definition: In a rightmost derivation, the rightmost variable is always expanded first: S ABC ABcC ABc AbBc AbbBc Abbc aAbbc abbcDerivation Trees Consider Derivation 1, the tree can be constructed as follows: S A B C a A b B c C ε b B ε ε The yield of the tree is the final string obtained by reading the leaves of the tree from left to right, ignoring the ε’s (unless all the leaves are ε, in which case the yield is ε). The yield of the above tree is the string abbc, as expected. Ambiguity Consider the grammar, G = ({S}, {a, b}, {S→aSb, S→bSa, S→SS, S→ε},S). ‘abab’ can be derived from the grammar with two parse trees. S S a S b S S b S a a S b a S b ε ε ε Definition: A grammar G is ambiguous if there exists some string w ∈ L(G) for which there are two or more distinct derivation trees, or there are two or more distinct leftmost derivations, or there are two or more distinct rightmost derivations. Definition: An inherently ambiguous language is a language for which no unambiguous grammar exists.Push Down Automata Definition: A nondeterministic pushdown automaton or NPDA is a 7-tuple M = (Q, ,Γ,δ, q0, z, F) where Q, is a finite set of states,  is the input alphabet, Γ is the stack alphabet, δ is the transition function, q0 ∈ Q, is the initial state, z ∈Γ is the stack start symbol, and F ⊆ Q is a set of final states. The transition function δ is defined as Q x ( ∪ ε) x Γ → Q x Γ* Definition: An instantaneous description of a pushdown automaton is a triplet (q, w, u), where q is the current state of the automaton, w is the unread part of the input string, and u is the stack contents (written as a string, with the leftmost symbol at the top of the stack). Definition: A grammar is in Chomsky Normal Form if all productions are of the form A→BC or A→a Where A, B, and C are variables a is a terminal. Definition: A grammar is in Greibach Normal Form if all productions are of the form A→ax Where a is a terminal x ∈V*.Converting from CFG to NPDA Idea: Any string of a context-free language has a leftmost derivation. So, set up the NPDA so that the stack contents "correspond" to this sentential form; every move of the NPDA represents one derivation step. ____ abb ABz | aabbb • Start state q0 just gets things initialized. Create a transition from q0 to q1 to put the grammar's start symbol on the stack. δ (q0, ε, z) →{(q1, Sz)} • State q1 does the bulk of the work, represent every derivation step as a move from q1 to q1. • Use the transition from q1 to qf to accept the string. δ (q1, ε, z) →{(qf, z)} Example: Consider the grammar G = ({S, A, B}, {a, b}, P, S), where P = {S→a, S→aAB, A→aA, A→a, B→bB, B→b}. Rearrange the production S→aAB as δ (q1, a, S)→ {(q1, AB)} Initial Step δ (q0, ε, z) → {(q1, Sz)} S→a,  δ (q1, a, S)→ {(q1,ε)} S→aAB,  δ (q1, a, S)→ {(q1, AB)} A→aA, δ (q1, a, A)→ {(q1, A)} A→a,  δ (q1, a, A)→ {(q1,ε)} B→bB,  δ (q1, b, B)→ {(q1, B)} B→b  δ (q1, b, B)→ {(q1,ε)} Accept Stepδ (q1, ε, z) → {(qf, z)}  Stack Characters remaining Characters readFor example, the derivation S  Aab  aaB  aabB  aabb maps into the sequence of moves (q0, aabb, z) | (q1, aabb, Sz) | (q1, abb, ABz) | (q1, bb, Bz) | (q1, b, Bz) | (q1, ε, z) | (q2, ε,


View Full Document

MIT 16 070 - Recitation 11 Notes

Documents in this Course
optim

optim

20 pages

Load more
Download Recitation 11 Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Recitation 11 Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Recitation 11 Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?