0 votes 0 votes Why in DPDA acceptance by empty stack and acceptance by final state is not equivalent ? How this prefix property plays important role ? Theory of Computation theory-of-computation made-easy-test-series pushdown-automata + – Chhotu asked Nov 25, 2017 edited Mar 3, 2019 by adeebafatima1 Chhotu 563 views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments ankitgupta.1729 commented Nov 25, 2017 reply Follow Share @Red_devil , Thank you :) .. but If regular expression is (ab)+ which is ab(ab)* , Then Language will contain strings {ab , abab, ababab,...} but here in string 'abab' , it contains prefix 'ab' which is already in language..So I think L is not satisfying prefix property.. Please correct me.. 0 votes 0 votes Red_devil commented Nov 25, 2017 reply Follow Share thanks!!@ ankitgupta.1729 my mistake.. that was not right example. 0 votes 0 votes Shubhanshu commented Nov 25, 2017 reply Follow Share prefix property definition:- If a language does not contain proper prefix of any of its string then that language is said to have prefix property. L1 = {anbn / n>=0} // do not have prefix property, because epsilon is the prefix of every string in L1. L2 = {anbn / n >=1} // have prefix property there is no prefix of any string is present in L2. Why does the language not have prefix property not accepted by Empty stack? Is because, epsilon is one of the strings in the language, now on seeing epsilon, if we do nothing then z0 will be present in the stack which means stack is not empty. If we pop the z0, then other strings like "aaabbb" will not be accepted because after all the a's over stack must have z0 on top but since z0 is popped off there is no symbol present in the stack at that time. 3 votes 3 votes Please log in or register to add a comment.