2 votes 2 votes Construct the DPDA with empty stack and final state method for the language L = ${ a^n b^n / n>= 0}$. Theory of Computation theory-of-computation pushdown-automata context-free-language + – Shubhanshu asked Aug 28, 2017 Shubhanshu 2.6k views answer comment Share Follow See all 7 Comments See all 7 7 Comments reply Show 4 previous comments Bikram commented Aug 31, 2017 reply Follow Share @ Shubhanshu A language has prefix property means if w∈L, then no proper prefix of w∈L. see this https://gateoverflow.in/35419/identify-language https://gateoverflow.in/377/gate1999_1-6 0 votes 0 votes Shubhanshu commented Aug 31, 2017 reply Follow Share Yes sir, the above language also do not satisfy the prefix property. as L contain L = { epsilon, ab, aabb, aaabbb, ....................} so if we take any string from this language lets say ab, then prefix of ab will be: epsilon, //proper prefix a, //proper prefix ab. //prefix since {epsilon} belongs to the language L, that;s why the language does not have prefix property, But why we can't draw its DPDA with empty stack.??? 0 votes 0 votes AakS commented Oct 12, 2017 reply Follow Share @Shubhanshu If a language L is accepted by the empty-stack DPDA M then it must be having prefix property. Suppose language L, that not following prefix property, is accepted by DPDA M using empty stack and uv ∈ L and also u ∈ L. Since u is accepted by M, there is computation path from (q0,u,S0) to (qk,ϵ,ϵ). Since M is deterministic, the only possible computation for input uv is (q0,u,S0) ⇒∗ (qk,v,ϵ). But M has already had empty stack and so it cannot move further from (qk,v,ϵ) and hence does not accept uv. 5 votes 5 votes Please log in or register to add a comment.