L = {a * b *}は通常の言語として分類されますか？

Question

L = {a * b *}は通常の言語として分類されますか？

私はL = {a^n b^n}が正規でないことを知っているので混乱しています。クレーネ星はどのような違いがありますか？

Answer 1

L = {a^n b^n}とL = {a*b*}があると、違いがあります。 {aaabbb, ab, aabb, etc}：あなたはそれはあなた言語であるa^n b^n言語を持っている場合

ははa'sとb's例の数が同じでなければなりません。あなたが言ったように、これは正規表現ではありません。

しかし、L = {a*b*}について言えば、aの任意の数字の後にb（0を含む）の任意の数字を付けることができます。いくつかの例です：

{a, b, aaab, aabbb, aabbbb, etc} 

あなたはそれはあなたがa'sとb'sの同じ番号を持つために必要な{a^n b^n}言語と異なる見ることができるように。

はいはいa*b*は本質的に規則的です。それは規則的であるなぜあなたは良い説明をしたい場合、あなたは彼らが、その後、より良い説明があるかもしれません。このHow to prove a language is regularを確認することができ、私（：

私はそれはあなたの

Answer 2

Bがある正規表現で記述言語を助け願っていますこれらの表現は、非正規言語を記述することはできず、実際には正規言語を定義する方法の1つです。（これは、正式な言語の定義方法の1つです。一方で、それを記述する）は、正規表現では記述できません。直感的に、aとbの境界に到達すると、 nを思い出してください。有界ではないので、有限記憶装置はそれを行うことができない。 bでは、これからはbのみが表示されることを覚えておく必要があります。これは非常に有限です。ある意味での2つの星は関連していません。それぞれは、そのブロックを他のブロックとは独立して拡張します。