Deterministic FA/ PDA Sequential Machine Theory Prof. K. J. Hintz Department of Electrical and Computer Engineering Lecture 4 Updated by Marek Perkowski Numerical Acceptor A Non-intuitive Concept of a Language Is One Which Can Accept Binary Arithmetic Values, e.g. L x B * : x 5 n, n 0 4 0 1 0 1 0 1 2 1 1 0 5 1 0 3 Moret, Theory of Computation Check all strings, from shortest that are accepted. What is their language? Languages Accepted by FA • The Class of Languages Accepted by a Deterministic or Nondeterministic FA Is Closed Under – – – – – Union Concatenation Kleene Star Complementation Intersection Union of Languages L = L 1 L since languages are sets of strings 2 M1 e > F = F1 F 2 e M2 Final States of N D FA Concatenation of Languages L = L1L 2 A ny elem ent of L w ith an elem ent of L > e F = F2 1 can be concatenated 2 S1 M1 F1 e S1 M2 F2 Final States of N D FA Kleene Star of Languages L = L1* A ny elem ent of L e > 1 can be K leene Starred e e S1 q0 F = F1 q 0 M1 F1 Final States of NDFA Difference of Languages L = L1 L 2 L1 F = F1 F 2 since languages are sets of strings L2 Final States of N D FA Intersection of Languages L = L 1 L L1 2 since languages are sets of strings L L2 F = F1 F2 F1 F2 F2 F1 Final States of NDFA I* Languages and FA • Kleene’s Theorem – A Language Is Regular iff It Is Accepted by a Deterministic or Nondeterministic Finite Automata • A Regular Language Is One Which Can Be Defined by a Regular Expression – Not all languages are regular Give examples of languages that are not regular Context Free Languages • Up Until Now we learned the following: R egular E x pression R egular Languages D F A N D F A But This Is a Limited Class of Languages • There Are Other Context-Free Languages Which Cannot Be Recognized by a DFA • There Are Other Types of Machines Which Can Accept More Context-Free Languages A Non-Regular Language • Since a Language, L, Is a Subset of the Set of All Strings, I*, Are There Some Strings Which Cannot Be Produced by a Regular Expression or Recognized by a DFA? Yes, e.g., n n L a b : n 0 n n a b Regular? • Theorem1: Let L be an infinite regular language. Then there are strings x, y, and z such that y e and x yn z L for each n 0 – Proof based on pigeonhole principle • If there are n + 1 pigeons and n pigeonholes, then at least two pigeons must be in the same hole – If a string has more characters than there are states in the language recognizer, then some state must be entered more than once 1 Lewis & Papadimitriou, Elements of the Theory of Computation n n a b Regular? L a b : n 0 n n • Language Is Infinite, Therefore Theorem Applies • Is This Language Regular? If So, the Theorem Must Apply • Three Cases to Study see next slides n n a b Regular? Case 1: y consists entirely of as xa p p0 ya q q0 za b r s r0 then L must contain x y za n p nq r b s n0 at most one of these strings can have an equal number of a s and b s n n a b Regular? Case 2: y consists entirely of bs Similar argument to Case 1 n n a b Regular? Case 3: y contains both as and bs For n > 1, x yn z has an occurrence of b preceding an occurrence of a and therefore cannot be in L Context Free Grammars: idea • A More General Way to Describe and/or Generate Languages • Context-Free – Replacement Rules Can Be Applied Independently of the Preceding or Following Elements. A aa B q abA aB c ab aa aB c ab aa aqc abA ac ab A aqc ab aa aqc Context Free Grammar: definition A Quadruple, ( I, , R, s) where I R An alphabet A set of terminals, I A finite set of rules, a subset of the crossproduct of the set of non-terminals and all strings, R I I * Context Free Grammar: definition cont s The start symbol, a non-terminal s I I AND ... The set of non-terminals Context Free Grammar: definition cont A I For All Non-terminals, u I* And Strings The Grammar, G, Maps the Non-Terminals to Strings A u G for strings and non-terminals u, v, x, y, v’ I* A I Context Free Grammar: definition of G-related u is G-related to v u v G iff u=xAy v = x v’ y and A v G Context Free Grammar: the set of all possible relations • The relation, , the * meaning the set of G all possible relations, is – reflexive – transitive – has closure u u G u v, v w, I* th en , G u w Context Free Language • The Language Generated by the Context Free Grammar, G, Is the Set of Strings Which Map From the Start Symbol, s, Under the Reflexive, Transitive, and Closed Relation, Language G w I * : s w G Context Free Language • A Context Free Language Is One Which Can Be Generated by a Context Free Grammar, and, • The Context Free Grammar (CFG) Can Be Used to Generate Strings of the Language A Derivation Example • The Steps in Applying the Rules From the Start Symbol to Any String Is Called a Derivation in G, e.g., I a , b, c, d , r , p, q, t , v , w a , b, c, d , r s w p ra q ab R t cad v qp w vtv s w vtv qptqp qratqra abratabra abracadabr a Pushdown Automata • All Context-Free Languages can Be Recognized by a PDA • { an bn } Is Context-Free, but Not Regular – Problem is same number of as and bs • PDA Assumes – An unlimited memory in the form of a stack, LIFO – The machine only has access to the top of the stack. Pushdown Automata: formal definition A PDA is a Sextuple, PDA S I S , I , , , s, F , w here A finite set of S tates inputs , alphabet stack sym bols A non - determ inistic push - dow n relation s T he unique start state F final states Pushdown Relation s are w ritten as S I * * S * present state, input string, top of stack , nex t state, new top o f stack where “top of stack” is replaced by “new top of stack.” Pushdown Relation Example p , , , q , R eplace th e on top of the x stack w ith x s=p s=q p , , , q , a push, i. e., replace the null on the top of the stack w ith a x a x s=p s=q PDA Properties • One Can Have the Same State Before and After a Transition, but Have Different Stack Contents Which Makes It NonDeterministic p , i, p, • State Changes May Occur in the Absence of an Input, but Only If the Stack Is Not Empty. i.e., non-causal behavior. PDA Properties: what is the state of PDA? • The “State” of the PDA Is Determined Not Only by S, and Not Only by the Top-ofStack, but Rather by Both the Current State and the Complete Contents of the Stack, x • This “State of the PDA” Is Called the “Configuration of the PDA” PDA Notation • The Input May Cause the PDA to Change From Configuration 1 to Configuration 2 s1 , x 1 y s2 , x 2 w here y I* s1 , s 2 S x 1 , x 2 *, the set o f all possible stack contents PDA Recognizer • A string w I* is accepted by a PDA iff some final state, s f F , and some string of stack symbols, where the input string, w I * such that w s 0 , s f , may occur * PDA Example* A Machine to Recognize Strings of the Form wcwR i. e. , L * Lewis & Papadimitriou, pg. 114 w cw R : w a, b * PDA Example wcwR Can Be Represented by a Context Free Grammar, G I, , R , S w h ere I R S , a , b, c a , b, c S aSa , S b S b, S c Equivalent NPDA wcwR can be represented by a NPDA where p , , , q , S q , , S , q , a S a q , , S , q , b S b q , , S , q , c q , a , a , q , q , b , b , q , q , c , c , q , T1 , p u sh n o n - term in al T 2 , ex p an d N T o n T O S T3 , ex p an d N T o n T O S T 4 , rep lace N T w ith c T5 , p o p a T6 , p o p b T7 , p o p c Is abccba Accepted? Present State Unread Input p abccba e - Initial Conf q abccba S T1 Push NT q abccba aSa T2 Pick T2/T3/T4 q bccba Sa T5 pop a Stack Transition (Top on Left) used Comments Is abccba Accepted? Present State Unread Input q bccba bSba T3 Pick T2/T3/T4 q ccba Sba T6 pop b q ccba cba T4 replace NT with c q cba ba T7 pop c Stack Transition (Top on Left) used Comments Is abccba Accepted? The machine halts with unread inputs since there is no q , c , b , next state, top of stack to be executed. Is bacab Accepted? Present State Unread Input p bacab e - Initial Conf q bacab S T1 Push NT q bacab bSb T3 Pick T2/T3/T4 q acab Sb T6 pop b Stack Transition (Top on Left) used Comments Is bacab Accepted? Present State Unread Input q acab aSab T2 Pick T2/T3/T4 q cab Sab T5 pop a q cab cab T4 replace NT with c q ab ab T7 pop c Stack Transition (Top on Left) used Comments Is bacab Accepted? Present State Unread Input Stack Transition (Top on Left) used Comments q b b T5 pop a q e e T6 pop b The machine halts with no unread input and nothing on the stack, therefore, bacab language wcwR.

Descargar
# ECE-548 Sequential Machine Theory