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 ?

  • $\begingroup$ Please don't re-ask the same question multiple times. $\endgroup$
    – D.W.
    Nov 30, 2023 at 5:40
  • $\begingroup$ 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. $\endgroup$ Nov 30, 2023 at 16:25
  • $\begingroup$ 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 $\endgroup$ Nov 30, 2023 at 16:31
  • $\begingroup$ 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) $\endgroup$ Nov 30, 2023 at 16:32


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.