CODEWITHSUNDEEP
formal-languagesautomatonpushdown-automatonjflap
Viktor
Viktor

Reputation: 59

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

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

Upvotes: 0

Views: 173

Answers (1)

Patrick87
Patrick87

Reputation: 28322

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.

Upvotes: 0

Related Questions