Home / Questions / 282562
Accepted
k1k4ss0
Asked: 2020-07-31 03:21:51 +0800 CST 2020-07-31 03:21:51 +0800 CST

Is L={ w ∈ ∑* / w ending in a} a regular language?

  • 772

I am trying to prove with the pumping lemma if the expression described in the title is a regular language or not, this is what I have tried:

∑={a,b}

∃(w)∈L y w = a^i b^j a  , siendo i,j>=0

|w| = 2n+1 >=n , cumple la condicion de |w| >= n

We know that w = xyzwith which:

|xy| <= n   ^   1 <= |y| <= n

Being X=a^p, y=a^qand that p+q<=n I would stay in the endz=a^(n-p-q) b^n a

This way it would stay|w|= p+q+n-p-q+n+1

checking the property of: x y^j z ∈ Lfor all j >=0, we have to create a new chain with j=2: w' = x y^2 zwith which it would be:

p + 2q + n - p - q + n + 1 =  2n + 1

In the end it is simplified to: q+2n+1 = 2n+1 that is only true if q=0which cannot be since the property of the pumping lemma itself says1<=|y|<=n

What I don't understand is that if I apply this with a string, for example:

w = aaaba

With n=2we can divide winto:

x=a
y=a
z=aba

With which for any y^ithat occurs to us as long as it is >=0, it should be accepted, since it ends in ano ??

regex

1 Answers

  1. Best Answer

    What is a regular language?

    A language that can be generated from a regular grammar, or that can be recognized by a regular expression.

    What is a regular grammar?

    It is a set formed by:

    • An alphabet (represented by ∑) that is nothing more than a set of symbols, in this case the symbols "a" and "b". These are terminal symbols because once one of them has been used, it is no longer "expanded" to generate others. ε, which represents the empty string, is also considered a terminal sign.
    • A set of "non-terminal symbols" (denoted by N) which are symbols that we will use to represent "sub-strings" of the language, so to speak, not yet terminated, while we are generating them.
    • A set of rules (denoted by P) that tells how each nonterminal symbol can be converted to another (terminal or nonterminal). Definitions can be recursive, a non-terminal symbol can generate an expansion that contains itself.
    • A non-terminal symbol with which production is started.

    Is your case a regular language?

    Yes, because it can be generated by the following regular grammar:

    • Vocabulary ∑={a,b}
    • Non-terminal symbols N={S, A}. The symbol S represents the start.
    • Rule set P as follows:
      • S -> A
      • A -> aA
      • A -> bA
      • A -> ε

    Starting with S, the rule tells me that I can expand it as "the non-terminal symbol A", followed by the character "a". The non-terminal symbol "A" in turn can be expanded either as the empty string, or as a letter "a" followed again by the symbol A (which can be expanded again by any of its rules, and so on), or either as a letter "b" followed again by the symbol A (which can again be expanded, etc.)

    This grammar generates strings like "a", "aa", "ba", "abbaabbababa", etc. This language would be recognized by the regular expression [ab]*a.

    Due to the first rule of P, all strings in the language will always end in a.

    So the pumping motto?

    The pumping lemma says that if a language is regular, then there must be a minimum length nsuch that any string of that length has a "central part" so to speak, which can be repeated as many times as desired, and the result it will remain part of the regular language.

    In this case the minimum length is 2. Any string of length 2 or greater in this language ends with "a", and can be written in the form xyz, where x=ε (empty string), y=all letters except "a " final, and finally z=a(the final "a"). Repeating yas many times as we want: xy^jza string ending in "a" will continue to appear, which will be part of the language.

    The pumping lemma is often used to prove that a language is not regular, by looking for a string that cannot be decomposed in this way. Since in this case we have a regular language, the pumping lemma is of no use, we will not be able to find such a counterexample.

    Your mistake I think was in equality:

    p + 2q + n - p - q + n + 1 =  2n + 1

    In it you are trying to make the lengths of the strings equal after the pump (ie after repeating the part y2 times) and before the pump , when yit appeared only once.

    Of course it is impossible for both lengths to coincide, unless you pump zero times or the length of yis zero. There is no reason to assume that these lengths are equal. In fact, no regular language would comply.

    • 23