Question

Given a language ba2nb where n > 1. How many different ways are there to choose the substring y when applying the pumping l

0 0
Add a comment Improve this question Transcribed image text
Answer #1

Given string is bna2nbn where n > 1

The strings accepted by a language are L = { bbaaaabb , bbbaaaaaabbb , bbbbaaaaaaaabbbb , ....................................soo on}

we can pick any one of the strings to apply pumping lemma.

let us consider the string s = bbbaaaaaabbb

The substring y might changes based on the string choosen

Different automatas follow different rules for applying pumping lemma.

we can make this language possible by using context free language.

The rules are as follows to apply pumping lemma for context free language.

If a language L is context-free, then there exists some integer p ≥ 1 such that any string s in L with |s| ≥ p (where p is a "pumping length") can be written as

s = uvxyz ( our example: bbbaaaaaabbb )

with substrings u, v, x, y and z, such that

  1. |vxy| ≤ p,
  2. |vy| ≥ 1, and
  3. uvnxynz is in L for all n ≥ 0.

There are number of chances to select y as a substring by following this rules.

NOTE:As mentioned above it is also dependent on the length of the string.

Add a comment
Know the answer?
Add Answer to:
Given a language b"a2nb" where n > 1. How many different ways are there to choose the substring y when apply...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT