# Is it Regular Language?

According to Wikipedia, Regular Language is Recognized by Some DFAs, or expressed by Regular Expression .. and all finite Language are regular but, not all regular is finite ..

that's mean it may be infinite language is regular ?

my example is L = {a^n b^n+1, n >0 } is it regular ? it generate infinite set of strings how to represent it as DFA or a regular expression (can represent this language using RegExp ?).. i can guarantee the exact number, how to automata to maintain the exact number of a's or b's

i tried some grammar, i do not get the regular grammar .. my grammar looks like

S -> AB

A -> aA | e

B -> bbB | e

final question, how the language is regular and infinite in the same time ?

• To answer a question in your text: $\{a^n, n\geq 0\}$ is infinite and regular. It is described by the regular expression $a^*$, so it can also be described by a finite automaton. Jan 19, 2015 at 7:41

Here's a derivation in your grammar, assuming that your 'e' denotes the empty string: $$S\Rightarrow AB\Rightarrow B\Rightarrow bbB\Rightarrow bb$$ This is clearly not in $L=\{a^nb^{n+1}\mid n>0\}$. There is, however, a non-regular grammar for your language: \begin{align} S&\rightarrow AB\\ A&\rightarrow aAb\mid ab &\text{generates a^nb^n}\\ B&\rightarrow b &\text{generates the b on the right} \end{align} There is no regular grammar that will generate $L$, since $L$ is not a regular language.
This does not, however, imply the converse: "If a language is regular, then it is finite." To see this, consider the true statement "If a number is a multiple of 6, then it is even". That's certainly true: 42 is a multiple of 6 and is also even. However, the converse, "If a number is even, then it is a multiple of 6" is certainly false sometimes, since 10 is even but not a multiple of 6. In logical notation, we have that the truth of $P\rightarrow Q$ does not guarantee that $Q\rightarrow P$.
The statement "If a language is finite, then it is regular" just says that the set consisting of finite languages are a subset of the set of regular languages, not that the two sets are the same. For example, the language $\{a^n\mid n\ge 0\}$ is regular (since that language is denoted by the regular expression $a^*$ and also generated by the grammar $S\rightarrow aS\mid \epsilon$) but is obviously not finite.
• @Yassine. It's not a silly question at all. The answer, though, isn't simple, even for languages of the form $a^nb^m$ where there's some relation between $n$ and $m$. For example, if $n=2m$ the language isn't regular, but if we just require $n+m$ to be even, then the language is regular. I suspect you'll learn a lot more about this and similar questions shortly. Jan 18, 2015 at 21:50