2y ago

21 Views

3 Downloads

710.47 KB

26 Pages

Transcription

Human-awareRoboticsContext FreeLanguages 2017/10/05 Chapter 2 in SipserØ Announcement:qLast call for responding to Poll #2qSlides will be put on BB1

RoboticsReview of Human-awareCFL Context free langaugesoContext free grammarsq Design CFGsq Ambiguitiesq Chomsky normal formoFA (DFA & NFA) expressRegular Expressions (RE)CFLPushdown automataq Definition of PDAq Computation PDAq Design of PDAq PDA and CFGq DPDA vs NPDAoNon-context free languagesq Limitations of CFLsq Pumping lemma for CFLq Closure properties for CFL2

RoboticsReview of Human-awareCFL Context free langaugesoContext free grammarsq Design CFGsq Ambiguitiesq Chomsky normal formoFA (DFA & NFA) expressRegular Expressions (RE)CFLPushdown automataq Definition of PDAq Computation PDAq Design of PDAq PDA and CFGq DPDA vs NPDAoNon-context free languagesq Limitations of CFLsq Pumping lemma for CFLq Closure properties for CFL3

Exercise Human-aware Robotics4

Exercise Human-aware Roboticsb. S - 1A1 0A0 1 0A - 1A 0A "c. S - 1S1 0S0 1S0 0S1 1 05

CFL are closed under:Human-awareExercise1. UnionRobotics2. Concatenation3. Star4. Intersection with regular languages (Problem 2.18)6

CFL are closed under:Human-awareExercise1. UnionRobotics2. Concatenation3. Star4. Intersection with regular languages (Problem 2.18)a. S - ABA - aA "B - bBc "b. Proof by contradiction: key Ā [ B̄7

Exercise Human-aware Robotics8

Exercise Human-aware Roboticsa. L1 U L2 whereL1 {concatenation of 3 arbitrary-length (including zero length) strings of zeros}L2 {0k#02k}b. Using pumping lemma or closure property9

Exercise Human-aware Robotics10

Exercise Human-aware RoboticsS ! SS "11

Exercise Human-aware RoboticsS ! SS "a. S - (S) "b. The correct solution would be S0 - S0S "12

Exercise Human-aware Robotics13

Exercise Human-aware Roboticsa. {anbn}b. w 0 w 1 a, b w 2 aa, ba, bb w 3 aaa, aab, aba, abb, baa, bab, bba, bbb w 4 Using induction to prove that the complement is anbn14

RoboticsReview of Human-awareCFL Context free langaugesoContext free grammarsq Design CFGsq Ambiguitiesq Chomsky normal formoFA (DFA & NFA) expressRegular Expressions (RE)CFLPushdown automataq Definition of PDAq Computation PDAq Design of PDAq PDA and CFGq DPDA vs NPDAoNon-context free languagesq Limitations of CFLsq Pumping lemma for CFLq Closure properties for CFL15

Exercise Human-aware Robotics16

Exercise Human-aware Robotics17

Exercise Human-aware Robotics18

Exercise Human-aware Robotics19

Exercise Human-aware Robotics20

Exercise Human-aware RoboticsUse PDA Q and DFA D to construct a new PDA Q’State space Q’ Q X DUsing Q’ to simulate both Q and D (what is the start state?)Accept only if both Q and D accept21

RoboticsReview of Human-awareCFL Context free langaugesoContext free grammarsq Design CFGsq Ambiguitiesq Chomsky normal formoFA (DFA & NFA) expressRegular Expressions (RE)CFLPushdown automataq Definition of PDAq Computation PDAq Design of PDAq PDA and CFGq DPDA vs NPDAoNon-context free languagesq Limitations of CFLsq Pumping lemma for CFLq Closure properties for CFL22

Exercise Human-aware Robotics23

Exercise Human-aware RoboticsHow about {0n1m0n1m}?24

Exercise Human-aware RoboticsHow about {0n1m0n1m}? Use closure property25

RoboticsOutline forHuman-awaretoday Context free langaugesoContext free grammarsq Design CFGsq Ambiguitiesq Chomsky normal formoFA (DFA & NFA) expressRegular Expressions (RE)CFLPushdown automataq Definition of PDAq Computation PDAq Design of PDAq PDA and CFGq DPDA vs NPDAoNon-context free languagesq Limitations of CFLsq Pumping lemma for CFLq Closure properties for CFL Reading assignment for the next class:o Enjoy your fall break and don’t forgetabout the project!o Sipser Sec. 3.1 – Quiz link will be sent out;due date is before the beginning of thenext class after fall break26

q Closure properties for CFL CFL Review of CFL. Human-aware Robotics 3 FA (DFA & NFA) express Regular Expressions (RE) Context free langauges o Context free grammars q Design CFGs q Ambiguities q Chomsky normal form o Pushdown automata q Definition of PDA q

Related Documents: