Let Σ = { a; b} How can I define a PDA in JFLAP which recognizes the following?

Question

L = {a^n b^k | 2n >= k}

For example.: abb is element of L, aabbb is element of L, ε is element of L, but babbb is not element of L, abbb is not element of L

Answer 1

The shortest string in L is the empty string, e. Given a string s in the language, the following rules hold:

1. as is in L
2. asb is in L
3. asbb is in L

We can combine these observations to get a context-free grammar:

S := aSbb | aSb | aS | e

By our observations, every string generated by this grammar must be in L. To show that this is a grammar for L, we must show that any string in L can be generated. To get a string a^n b^k we can do the following:

1. use rule #1 above x times
2. use rule #2 above y times
3. use rule #3 above z times
4. ensure x + y + z = n
5. ensure y + 2z = k

Setting y = k - 2z and substituting we find x + k - 2z + z = n. Rearranging:

1. if k > n, then z and x can be chosen however desired so long as k - n = z - x.
2. if k < n, then z and x can be chosen however desired so long as n - k = x - z.
3. If k = n, observe we might as well just choose y = n.

Note that we can always choose z and x in our above example since 0 <= x, z <= n and 0 <= k <= 2n.