3

Can someone help me design PDA for {a^n b^m | n<=m<=2n}. Can you please design one with explanation.

RJ Naskar
  • 31
  • 1
  • 2
  • What have you tried already? – promaxdev Jun 01 '21 at 05:14
  • Have you tried to see if it is context-free? If you pop 1 'a' for every 'b' scanned, you would empty the stack when you have scanned equal number (n) of 'a's and 'b's. After that you need to make sure that all the remaining 'b's don't exceed '2n'. Hope you got the clue. – promaxdev Jun 01 '21 at 05:26

2 Answers2

5

The idea here is this: read every a and push a symbol onto the stack for each one. Then, when you start reading b's, at each step, nondeterministically choose whether to read a single b and pop one stack symbol, or whether two read two b's and pop one stack symbol. Then, make the PDA accept if the input is exhausted and the stack is empty.

  • if you always choose to pop one stack symbol for each b read, then you get m = n
  • if you always choose to pop one stack symbol for every pair of b read, then you get m = 2n
  • if you sometimes choose to read one b and sometimes two, then you end up with n < m < 2n; n < m because sometimes you read more b than you had stack symbols for, m < 2n because sometimes you only read one b and popped from the stack

NPDAs accept if at least one path ends up accepting; so, as long as some pattern of guessing to read one or two b's for each stack symbol gets the right value of m, the string is accepted. It should be clear that for any value of m such that n <= m <= 2n, there is a solution to the linear system:

x + 2y = m
x + y = n

Here, x is the number of times the NPDA should guess that it reads one b, and y is the number of times the NPDA should guess that it reads two b's. We can subtract the 2nd from the 1st:

y = m - n

Because y must be nonnegative, we get our first condition, n <= m. Plugging this back into the 2nd origination equation gives:

    x + m - n = n
<=> x = 2n - m

Again, because x must be nonnegative, this gives our second condition, m <= 2n.

Patrick87
  • 27,682
  • 3
  • 38
  • 73
0

Nondeterministically, push one or two as into the stack in each reading of an a and then match the incoming bs with the pushed as.

javadr
  • 310
  • 2
  • 12