World's most popular travel blog for travel bloggers.

[Solved]: Is it Regular Language?

, , No Comments
Problem Detail: 

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 ?

Asked By : Yassine

Answered By : Rick Decker

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37366

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback