1
$\begingroup$

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 ?

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 19, 2015 at 7:41

1 Answer 1

2
$\begingroup$

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.

For your last question, "how can a language be regular and infinite?", you appear to be confused by your observation that any finite language is regular. This is true: logically we'd write this as "If a language is finite, then it is regular."

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.

$\endgroup$
3
  • $\begingroup$ can i say that every language that has for example a^n b^m whatever the value of n or m equal or not is not regular language ?? its looks like silly question sorry ... $\endgroup$
    – Yassine
    Jan 18, 2015 at 20:28
  • $\begingroup$ There are ways to determine whether a language is regular, for example the Pumping Lemma or the Nerode Relation. $\endgroup$
    – Jasper
    Jan 18, 2015 at 20:46
  • 1
    $\begingroup$ @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. $\endgroup$ Jan 18, 2015 at 21:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.