Automata-theory-regular-expressions

正規表現

• 正規表現*は、次のように再帰的に定義することができます-

• ε*は正規表現で、空の文字列を含む言語を示します。 *（L（ε）= \ {ε}）
• φ*は、空の言語を示す正規表現です。 *（L（φ）= \ {}）
• x は、 L = \ {x} の正規表現です
• X が言語* L（X）を表す正規表現であり、 *Y が言語* L（Y）*を表す正規表現である場合、
• X + Y は、言語* L（X）∪L（Y）に対応する正規表現です。ここで、 L（X + Y）= L（X）∪L（Y）*です。
• X . Y *は、言語 L（X）に対応する正規表現です。 L（Y）ここで L（X.Y）= L（X）。 L（Y）*
• R は、言語 L（R ）に対応する正規表現です。 L（R ）=（L（R））
• 1〜5のルールを何度か適用すると、それらは正規表現になります。

いくつかのREの例

Regular Expressions	Regular Set
(0 + 10*)	L = \{ 0, 1, 10, 100, 1000, 10000, … }
(0*10*)	L = \{1, 01, 10, 010, 0010, …}
(0 + ε)(1 + ε)	L = \{ε, 0, 1, 01}
(a+b)*	Set of strings of a’s and b’s of any length including the null string. So L = \{ ε, a, b, aa , ab , bb , ba, aaa…….}
(a+b)*abb	Set of strings of a’s and b’s ending with the string abb. So L = \{abb, aabb, babb, aaabb, ababb, …………..}
(11)*	Set consisting of even number of 1’s including empty string, So L= \{ε, 11, 1111, 111111, ……….}
(aa)*(bb)*b	Set of strings consisting of even number of a’s followed by odd number of b’s , so L = \{b, aab, aabbb, aabbbbb, aaaab, aaaabbb, …………..}
(aa + ab + ba + bb)*	String of a’s and b’s of even length can be obtained by concatenating any combination of the strings aa, ab, ba and bb including null, so L = \{aa, ab, ba, bb, aaab, aaba, …………..}