# Two Counter word count language Nondeterministic Pushdown Automata (NPDA) problem actually Context Sensitive unless counters are multiples

Classic text (Linz, P., & Rodger, S. H. (2022). An introduction to formal languages and automata. Jones & Bartlett Learning.) describes the following language where one is to describe an nondeterministic pushdown automata (chapter 8 problem 4j fifth edition) :

Describe a language over {a,b} where the count of b's is equal or between two times the number of a's and 3 times the number of b's or expressed as:

where L = { w: 2na(w) <= nb(w) <= 3na(w) }

consider a simplified version of this problem with a's only followed by b's could be addressed with the following NPDA (leveraging nondeterminism to support the range defined by both counters)

T (transitions)

T{S0, a, Z} -> {S0, aaa}
T{S0, a, a} -> {S0, aaaa}
T{S0, b, a} -> {S1, lam} {S1, lam}
T{S1, lam, a} -> {S0, lam} # loop back to support two 'pops' within two operations
T{S1, lam , Z} -> {S3, lam} final state (empty stack)

in english I push 3 a's and pop either 1 or 2 for b's However this defines a superset where scenarios such as word 'ab' is accepted by popping twice (the npda can follow this path to an empty stack and final state).

(NOTE: this language could be defined by changing the counters which are multiples of 2 such as where L = { w: 2na(w) <= nb(w) <= 4na(w) } because this language would be enforced by pushing 4 and popping 1 or 2 'as thus supporting a npda solution.)

My contention is the original definition of the range between 2 and 3 times the amount of a's cannot be defined by an npda (where the solution is only resolved with definition of a superset for reasons explained) - However the book implies this to be a language defined by npda?

Does another solution exists (outside of changing the range between 2-4x) which is not leveraging a TM or unrestricted / context sensitive grammar ?

• Please don't re-ask the same question multiple times.
– D.W.
Nov 30, 2023 at 5:40
• Thanks to all who have reviewed my question! To respond to all comments - i searched for a few days to which i still have not found an 'npda' based solution If there was specifically an npda (not CFG) published please let me know. Additionally i asked for symbol count not strict letters followed by symbols. In either case the posted link by Hendrik illustrated the flaw ( when converted from CFG to npda via greibach nornal form ) in my design which was to 'push either lower / upper limit' and 'pop' only one character at a time for input. Nov 30, 2023 at 16:25
• Here is my final NPDA solution ( as compared to my first approach ) for those who may try to solve by pushing the upper limit vs leveraging the nondeterminism for popping Nov 30, 2023 at 16:31
• T{S0, a, Z} -> {S0, aaa} T{S0, a, a} -> {S0, aaa}, {S0, aaaa} T{S0, b, a} -> {S1, lam} T{S1, lam , Z} -> {S2, lam} final state (empty stack) Nov 30, 2023 at 16:32