Test series

Question

As we know that, PDA=Finite Automata + one Stack. Assume a modified PDA M1 in which, in place of stack if we use counter (where counter is able to count the number of occurrences of terminals in input string), i.e., PDA M1 = Finite Automata + one counter.
Consider the given below languages:
L1={aⁿ bⁿ |n>0}
L2={ww^r| w ϵ {a,b}*}
L3= {w | n_a(w) = n_b(w)}
Which language can M1 recognize?

Comments

L1 and L3  can be recognized by PDA M1 but not L2, because

here counter can save no. of occurrence but can't save type of occurrence.

for L1, you only need to save count of occurrence of a's that can be later matched by count of b's,

for L3, you also need only count of occurrence, i will upload PDA later, you will get clear idea.

for L2, in addition to count of occurrence of 'a' and 'b' you also need to save type of occurrence(i.e 'a' or 'b') which you can't do with just a counter.

overall, if you can design PDA such that, only single stack alphabet is needed(excluding Z₀), then that language can be accepted by modified PDA M1

---

@ nitish

This is their solution-

Since counter is able to count the number of occurrences of terminals in an input string, but it doesn’t have the LIFO (last in first out) property of stack. So it can only recognize those language where the order of occurrence of terminals doesn’t matter, i.e., only count is required. As in L1={aⁿbⁿ |n>0} and L2 ={ww^r| w ∈ {a,b}*} the order and count both matters hence the modified PDA cannot recognize these languages. But in L3 only count matters hence M1 can recognize L3.

And can you please further elaborate as to how a single counter can keep track of both number of a's as well as b's in L3 since they can come in any random order?

---

How can we compare count of a's with b's ...even after tracking number of a's in string..means how FA will.compare the count...since stack is not given

Not able to understand?

---

M1 is able to recognize L1 and L3 but cannot recognize L2.

right?

---

a push down automata contains an FA and a stack here it has an FA but a counter hence we cannot recogonise the languages which EXPLICITLY NEED STACK PROPERTY LIKE L2    L1 can be handled even without STACK because the DFA will take care about it and sees that no B'S come after A'S hence for such inputs the dfa goes to the dead configuration hence L1 AND L3 is the answer

---

Still...means...for L3 , let the DFA save number of a's at each stage how will it come to know that number of b's are same as number of a's . Logically, we can tell and PDA was able to do it because of push pop property of stack..

Here counter can just store numbers...how will DFA result in successfull parsing along with counter..

That's where I m confused still!

---

stack is a datastructure and counter here also functions similarly except for the push and pop functionality we dont need a stack to accept L1 we just need memory(infiite)  FA alone doesnt have it as it has finite memory if we give FA infinite memory we can design Finite automata for L1 its easy....

Answer 1

L1 and L3 are deterministic CFL But  L2 is Non Deterministic CFL

Comments

L1 and L3 correct answer..