finite automata - Proof the language is regular or not regular using Pumping lemma? -


can 1 figure out l = { am bn, m ≥ n + 2, m ≤ 3 } regular or not using pumping lemma, seems bit difficult prove.

i have tried used pumping lemma , shows regular language confused right or not.

i have tried used pumping lemma , shows regular language confused right or not.

first note, pumping lemma can used proof "certain language not regular language". can not use pumping lemma proof "certain language is regular".

yes, pumping lemma regular languages describes essential property of regular languages, , if languages don't satisfy conditions described pumping lemma or don't satisfy pumping lemma property language not regular language, converse of not true!! &mdash- there "languages satisfies pumping lemma's conditions , may still non-regular", means:-

pumping lemma 'necessary not sufficient condition' language regular.

like: every engineer math student - if student engineer can knows math, math students don't know engineering. (just giving example explain)

from question, have impression don't understand - "what regular language?".

unlike pumping lemma regular languages, need learn other characteristics of regular languages - finding them in language proofs language regular language. if can represent language using finite automata or/and regular expression proofs language regular language.

now, come original question:

how proof language { am bn, m ≥ n + 2, m ≤ 3 } regular or not?

because neither 'm' or 'n' can negative (a string without occurrence of symbol possible eg. empty string1, string negative occurrence of language symbols not possible) , according condition "m ≥ n + 2", 'm' greater 'n' — minimum value of 'm' (when 'n' 0) 2. second condition "m ≤ 3", maximum value of 'm' '3', , 'm' can either 2 or 3.

if again notice fist condition: "m ≥ n + 2" m = {2, 3} possible values 'n' can be:

  • for m = 2, n can 0 , makes string 'aa'.
  • for m = 3, n can 0 or 1 , makes strings 'aaa', 'aaab'.

so, came language finite language e. consists of 3 strings. every finite language regular language, check venn diagram:

see venn-diagram

(to lean more read: finiteness of regular language)

regular expression language l = { am bn, m ≥ n + 2, m ≤ 3 } aa(a + λ)(b + λ), hence proofed language regular language.

1 string without occurrence of symbol called empty or null string in formal languages, in of formal language books symbol Ɛ empty string.
λ empty symbol.


Comments

Popular posts from this blog

google chrome - Developer tools - How to inspect the elements which are added momentarily (by JQuery)? -

angularjs - Showing an empty as first option in select tag -

php - Cloud9 cloud IDE and CakePHP -