در علوم نظری رایانه، زبان های منظم، به زیرمجموعه ای از زبان های صوری گفته می شود.
اعضای یک زبان منظم با عبارت های منظم ساخته می شوند و توسط ماشین حالت متناهی معین پذیرفته می شوند. از زبان های منظم در تجزیه کننده ها و طراحی زبان های برنامه نویسی استفاده می شود.
مجموعهٔ زبان های منظم روی یک الفبا مثل Σ ، به صورت بازگشتی زیر تعریف می شود:
• زبان بدون رشته، ∅ {\displaystyle \emptyset } ، یک زبان منظم است.
• برای هر عضو الفبا، a ∈ Σ {\displaystyle a\in \Sigma } ، مجموعهٔ تک عضوی { a } {\displaystyle \{a\}} ، یک زبان منظم است.
• اگر مجموعه های A {\displaystyle A} و B {\displaystyle B} دو زبان منظم باشند، آنگاه اجتماع آن ها ( A ∪ B ) {\displaystyle ( A\cup B ) } ، الحاق آن ها ( A ∩ B ) {\displaystyle ( A\cap B ) } وستاره کلین ( A ∗ {\displaystyle A^{*}} ) زبان های منظم هستند.
هر مجموعه ای شامل تعداد متناهی رشته یک زبان منظم است. مجوعهٔ تک عضوی شامل رشتهٔ تهی، { ϵ } یک زبان منظم است. به همین ترتیب، روی الفبای { a , b } ∗ ، زبانی که شامل تعداد برابر از حروف a و b باشد، یک زبان منظم است.
{ a n b n | n ≥ 0 } یک زبان منظم نیست. یعنی این زبان، زبان مورد پذیرش برای هیچ ماشین حالت متناهی نیست و نمی توان آن را با عبارت های منظم بیان کرد. برای نشان دادن آن که یک زبان، منظم نیست، از لم تزریق، استفاده می شود.
یک زبان منظم:
• زبان مورد پذیرش یک اتوماتون تعین ناپذیر متناهی، ( NFA ) است.
• زبان مورد پذیرش یک ماشین های تعین پذیر حالات متناهی، ( DFA ) است.
• زبان مورد پذیرش یک یک ماشین حالت متناهی متناوب، ( AFA ) است.
• توسط یک دستور منظم ( Regular grammar ) ، ساخته می شود.
• توسط یک دستور پیشوندی ( Prefix grammar ) ، ساخته می شود.
• زبان مورد پذیرش یک ماشین تورینگ است.
• قابل بیان در منطق مرتبهٔ دوم است.
• ( R ∗ ) ∗ = R ∗ {\displaystyle ( R^{*} ) ^{*}=R^{*}}
• ( ϵ + R ) ∗ = R ∗ {\displaystyle ( \epsilon +R ) ^{*}=R^{*}}
• R + R ∗ = R ∗ {\displaystyle R+R^{*}=R^{*}}
• R R ∗ = R + {\displaystyle RR^{*}=R^{+}}
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفاعضای یک زبان منظم با عبارت های منظم ساخته می شوند و توسط ماشین حالت متناهی معین پذیرفته می شوند. از زبان های منظم در تجزیه کننده ها و طراحی زبان های برنامه نویسی استفاده می شود.
مجموعهٔ زبان های منظم روی یک الفبا مثل Σ ، به صورت بازگشتی زیر تعریف می شود:
• زبان بدون رشته، ∅ {\displaystyle \emptyset } ، یک زبان منظم است.
• برای هر عضو الفبا، a ∈ Σ {\displaystyle a\in \Sigma } ، مجموعهٔ تک عضوی { a } {\displaystyle \{a\}} ، یک زبان منظم است.
• اگر مجموعه های A {\displaystyle A} و B {\displaystyle B} دو زبان منظم باشند، آنگاه اجتماع آن ها ( A ∪ B ) {\displaystyle ( A\cup B ) } ، الحاق آن ها ( A ∩ B ) {\displaystyle ( A\cap B ) } وستاره کلین ( A ∗ {\displaystyle A^{*}} ) زبان های منظم هستند.
هر مجموعه ای شامل تعداد متناهی رشته یک زبان منظم است. مجوعهٔ تک عضوی شامل رشتهٔ تهی، { ϵ } یک زبان منظم است. به همین ترتیب، روی الفبای { a , b } ∗ ، زبانی که شامل تعداد برابر از حروف a و b باشد، یک زبان منظم است.
{ a n b n | n ≥ 0 } یک زبان منظم نیست. یعنی این زبان، زبان مورد پذیرش برای هیچ ماشین حالت متناهی نیست و نمی توان آن را با عبارت های منظم بیان کرد. برای نشان دادن آن که یک زبان، منظم نیست، از لم تزریق، استفاده می شود.
یک زبان منظم:
• زبان مورد پذیرش یک اتوماتون تعین ناپذیر متناهی، ( NFA ) است.
• زبان مورد پذیرش یک ماشین های تعین پذیر حالات متناهی، ( DFA ) است.
• زبان مورد پذیرش یک یک ماشین حالت متناهی متناوب، ( AFA ) است.
• توسط یک دستور منظم ( Regular grammar ) ، ساخته می شود.
• توسط یک دستور پیشوندی ( Prefix grammar ) ، ساخته می شود.
• زبان مورد پذیرش یک ماشین تورینگ است.
• قابل بیان در منطق مرتبهٔ دوم است.
• ( R ∗ ) ∗ = R ∗ {\displaystyle ( R^{*} ) ^{*}=R^{*}}
• ( ϵ + R ) ∗ = R ∗ {\displaystyle ( \epsilon +R ) ^{*}=R^{*}}
• R + R ∗ = R ∗ {\displaystyle R+R^{*}=R^{*}}
• R R ∗ = R + {\displaystyle RR^{*}=R^{+}}
wiki: زبان منظم