7 votes 7 votes A language $L$ has the prefix property if there are no two distinct strings in $L,$ such that one is a prefix of the other. Which of the following language classes has/have prefix property? (Mark all the appropriate choices) Finite Languages Regular Languages Deterministic Context Free Languages Deterministic Context Free Languages accepted by Empty Stack Push Down Automata Theory of Computation go2025-toc-1 prefix-property multiple-selects + – gatecse asked Sep 29, 2020 gatecse 492 views answer comment Share Follow See 1 comment See all 1 1 comment reply diptanshu malviya commented Nov 4, 2023 reply Follow Share there are two link for the revision purpose (155) Lec 164 What is Prefix Property - YouTube https://youtu.be/r6fulNgV7L0 In the second link the timestamp of 36:26 / 38:14 conclude that every DPDA which is implimented through the empty stack method will always have a prefix property 1 votes 1 votes Please log in or register to add a comment.
Best answer 4 votes 4 votes Only deterministic CFL accepted by empty stack has prefix property. $L = \{a,aa\}$ is a simple counter example for the other three options as it does not satisfy the prefix property but is still finite and hence regular as well as DCFL too. gatecse answered Sep 29, 2020 • selected Sep 26, 2021 by Arjun gatecse comment Share Follow See all 4 Comments See all 4 4 Comments reply Vaibhav98 commented Oct 22, 2020 reply Follow Share can you please give the example of DCFL accepted by empty stack PDA or does the DCFL with the empty stack PDA accepts only null string 0 votes 0 votes abhishek.sharma9721 commented Feb 5, 2021 reply Follow Share @gatecse Sir is this question modification of prefix property becoz,Regular languages are closed under prefix property. 0 votes 0 votes Arjun commented Sep 26, 2021 reply Follow Share Prefix property of a language and “prefix” operation on a language are 2 things. 0 votes 0 votes JayRathi commented Jan 24 reply Follow Share I have learnt worng definition of prefix property that if language have strings which are prefix of each other . 0 votes 0 votes Please log in or register to add a comment.