In: Computer Science
Let L = {x = a^rb^s | r + s = 1mod2}, I.e, r + s is an odd number. Is L regular or not? Give a proof that your answer is correct.
Answer : the language L is NOT regular.
=> Some Points for regular and not regular :
1. Every finite set represents a regular language.
2. Given an expression of non-regular language, but the value of parameter is bounded by some constant, then the language is regular (means it has kind of finite comparison).
3. The pattern of strings form an
A.P.(Arithmetic Progression) is regular(i.e it’s power is in form
of linear expression),
but the pattern with G.P.(Geometric Progression) is not regular(i.e
its power is in form of non-linear expression) and it comes under
class of Context Sensitive Language.
4. No pattern is present, that could be repeated to generate all the strings in language is not regular.Finding prime itself is not possible with FA.
5. A concatenation of pattern(regular) and a non-pattern(not regular) is also not a regular language.
6. Whenever unbounded storage is required for storing the count and then comparison with other unbounded counts, then the language is not regular.
Reason for NOT regular language of L is :
=> the language is infinite (not finite).
=> There is no any pattern in strings of language.