GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 15

Question

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)

• A. Finite Languages
• B. Regular Languages
• C. Deterministic Context Free Languages
• D. Deterministic Context Free Languages accepted by Empty Stack Push Down Automata

Comments

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

Answer 1

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.

Comments

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

---

@gatecse Sir is this question modification of prefix property becoz,Regular languages are closed under prefix property.

---

Prefix property of a language and “prefix” operation on a language are 2 things.

---

I have learnt worng definition of prefix property that if language have strings which are prefix of each other .