Context-Free Grammars in CSE 311 Lecture
This content delves into Context-Free Grammars (CFG) in computer science, specifically focusing on their rules, uses, and examples. Understanding CFG is crucial for solving various language-related problems efficiently.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
[Audience looks around] What just happened? There must be some context were missing. xkcd.com/1090 Context Free Grammars CSE 311 Winter 2023 Lecture 22
What Cant Regular Expressions Do? Some easy things Where you could say whether a string matches with just a loop {0?1?:? 0} The set of all palindromes. And some harder things Expressions with matched parentheses Properly formed arithmetic expressions Context Free Grammars can solve all of these problems!
Context Free Grammars A context free grammar (CFG) is a finite set of production rules over: An alphabet of terminal symbols A finite set ?of nonterminal symbols A start symbol (one of the elements of ?) usually denoted ?. A production rule for a nonterminal ? ? takes the form ? ?1?2 |?? Where each ?? ? is a string of nonterminals and terminals.
Context Free Grammars We think of context free grammars as generating 1. Start from the start symbol ?. 2. Choose a nonterminal in the string, and a production rule ? ?1?2 |?? replace that copy of the nonterminal with ??. 3. If no nonterminals remain, you re done! Otherwise, goto step 2. generating strings. A string is in the language of the CFG iff it can be generated starting from ?. Notation: ??? ??? is rewriting ? with ?.
Examples ? 0?0 1?1 0|1|? ? 0?|?1|? ? ? ?? ? The alphabet here is {(,)} i.e. parentheses are the characters. ? ?? ? 0?1|? ? 1?0|?
Examples ? 0?0 1?1 0|1|? The set of all binary palindromes ? 0?|?1|? The set of all strings with any 0 s coming before any 1 s (i.e. 0 1 ) ? ? ?? ? Balanced parentheses ? ?? ? 0?1|? ? 1?0|?{0?1?+?0?:?,? 0}
Arithmetic ? ? + ? ? ? ? ? ? ? 0 1 2 3 4 5 6 7 8|9 Generate 2 ? + ? Generate 2 + 3 4 in two different ways pollev.com/robbie
Arithmetic ? ? + ? ? ? ? ? ? ? 0 1 2 3 4 5 6 7 8|9 Generate 2 ? + ? ? ? + ? ? + ? ? ? + ? 2 ? + ? 2 ? + ? (2 ?) + ? Generate 2 + 3 4in two different ways ? ? + ? ? + ? ? 2 + ? ? 2 + 3 ? 2 + 3 4 ? ? ? ? + ? ? 2 + ? ? 2 + 3 ? 2 + 3 4
Parse Trees Suppose a context free grammar ? generates a string ? A parse tree of ? for ? has Rooted at ? (start symbol) Children of every ? node are labeled with the characters of ? for some ? ? Reading the leaves from left to right gives ?. S 0 S 0 ? 0?0 1?1 0 1 ? 1 S 1 1
Back to the arithmetic ? ? + ? ? ? ? ? ? ? 0 1 2 3 4 5 6 7 8|9 Two parse trees for 2 + 3 4 E E E E E E E E E E E E + E E + 4 E E E E 2 E E 3 3 2 4
How do we encode order of operations If we want to keep in order we want there to be only one possible parse tree. Differentiate between things to add and things to multiply Only introduce a * sign after you ve eliminated the possibility of introducing another + sign in that area. E E E E T T + T T F F T T ? ?|? + ? F F N N F F ? ?|? ? N N ? ? |? 4 N N ? ? ? ? 0 1 2 3 4 5 6 7|8|9 3 2
CNFs in practice Used to define programming languages. Often written in Backus-Naur Form just different notation Variables Variables are <names-in-brackets> or technical terms like <if-then-else-statement>, <condition>, <identifier> is replaced with = or
Parse Trees Remember diagramming sentences in middle school? <sentence>::=<noun phrase><verb phrase> <noun phrase>::=<determiner><adjective><noun> <verb phrase>::=<verb><adverb>|<verb><object> <object>::=<noun phrase>
Parse Trees <sentence>::=<noun phrase><verb phrase> <noun phrase>::=<determiner><adjective><noun> <verb phrase>::=<verb><adverb>|<verb><object> <object>::=<noun phrase> The old man the boat.
The old man the boat By Jochen Burghardt - Own work, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=92742400
Power of Context Free Languages There are languages CFGs can express that regular expressions can t e.g. palindromes What about vice versa is there a language that a regular expression can represent that a CFG can t? No! Are there languages even CFGs cannot represent? Yes! {0?1?2?3?|?,? 0} cannot be written with a context free grammar.
Takeaways CFGs and regular expressions gave us ways of succinctly representing sets of strings Regular expressions super useful for representing things you need to search for CFGs represent complicated languages like java code with valid syntax Next Week, we ll talk about how each of these are equivalent to weaker computers. This week: Two more tools for our toolbox.
Relations Relations A (binary) relation from ? to ? is a subset of ? ? A (binary) relation on ? is a subset of ? ? Wait what? is a relation on . 3 4 is a way of saying 3 relates to 4 (for the relation) (3,4) is an element of the set that defines the relation.
Relations, Examples It turns out, they ve been here the whole time < on is a relation I.e. { ?,? ? < ? and ?,? }. = on is a relation i.e. { ?,? ? = ? and ?,? } For your favorite function ?, you can define a relation from its domain to its co-domain i.e. { ?,? ? ? = ?} ? when squared gives ? is a relation i.e. { ?,? :?2= ?,?,? }
Relations, Examples Fix a universal set ?. is a relation. What s it on? ?(?) The set of all subsets of ?
More Relations ?1= { ?,1 , ?,2 , ?,1 , ?,3 , ?,3 } Is a relation (you can define one just by listing what relates to what) Equivalence mod 5 is a relation. { ?,? ? ? ??? 5 } We ll also say x relates to y if and only if they re congruent mod 5
Properties of relations What do we do with relations? Usually we prove properties about them. Symmetry A binary relation ? on a set ?is symmetric iff for all ?,? ?, [ ?,? ? ?,? ?] = on is symmetric, for all ?,? if ? = ? then ? = ?. is not symmetric on ?(?) 1,2,3 {1,2,3,4} but 1,2,3,4 {1,2,3} Transitivity A binary relation ? on a set ?is transitive iff for all ?,?,? ?, [ ?,? ? ?,? ? ?,? ?] = on is transitive, for all ?,?,? if ? = ? and ? = c then ? = ?. is transitive on ?(?) for any sets ?,?,? if ? ? and ? ? then ? ?. is not a transitive relation 1 {1,2,3}, 1,2,3 ?( 1,2,3 ) but 1 ? 1,2,3 .
Warm up Show that ? ? ??? ? if and only if ? ?(??? ?) ? ? ??? ? ?|(? ?) ?? = ? ? for ? ?( ?) = ? ?(for k ) ?| ? ? ? ?(??? ?) This was a proof that the relation { ?,? ? ? ??? ? } is symmetric! Show that ?%?=(? ?)%? Where ?%? is the unique ? such that ? = ?? + ? for some integer ?. By definition of %, ? = ?? + (?%?) for some integer ?. Subtracting ?, ? ? = ? 1 ? + (?%?). Observe that ? 1 is an integer, and that this is the form of the division theorem for ? ? %?. Since the division theorem guarantees a unique integer, ? ? %? = (?%?) It was actually overkill to show if and only if. Showing just one direction turns out to be enough!
What about transitivity? Some quarters there s a homework problem we didn t have one this time. Divides is a transitive relation! If ?|? and ?|? then ?|?.
More Properties of relations What do we do with relations? Usually we prove properties about them. Antisymmetry A binary relation ? on a set ?is antisymmetric iff for all ?,? ?, [ ?,? ? ? ? ?,? ?] is antisymmetric on Reflexivity A binary relation ? on a set ?is reflexive iff for all ? ?, [ ?,? ?] is reflexive on
Youve proven antisymmetry too! Antisymmetry A binary relation ? on a set ?is antisymmetric iff for all ?,? ?, [ ?,? ? ? ? ?,? ?] You showed | is antisymmetric on + in section 5. for all ?,? ?, [ ?,? ? b,a ? ? = ?] is equivalent to the definition in the box above The box version is easier to understand, the other version is usually easier to prove.
Try a few of your own Pollev.com/robbie Decide whether each of these relations are Reflexive, symmetric, antisymmetric, and transitive. on ?(?) on > on | on + | on (??? 3) on Symmetry: for all ?,? ?, [ ?,? ? ?,? ?] Antisymmetry: for all ?,? ?, [ ?,? ? ? ? ?,? ?] Transitivity: for all ?,?,? ?, [ ?,? ? ?,? ? ?,? ?] Reflexivity: for all ? ?, [ ?,? ?]
Try a few of your own Symmetry: for all ?,? ?, [ ?,? ? ?,? ?] Antisymmetry: for all ?,? ?, [ ?,? ? ? ? ?,? ?] Decide whether each of these relations are Reflexive, symmetric, antisymmetric, and transitive. on ? ? reflexive, antisymmetric, transitive on reflexive, antisymmetric, transitive > on antisymmetric, transitive | on + reflexive, antisymmetric, transitive | on reflexive, transitive (??? 3) on reflexive, symmetric, transitive Transitivity: for all ?,?,? ?, [ ?,? ? ?,? ? ?,? ?] Reflexivity: for all ? ?, [ ?,? ?]
