تالار گفتمان مانشت

چطور هم منظمه و مستقل از متن؟
L={vwv: v,w{a,b}*, |v|=2} 93

سلام

زبانی که منظم باشه حتما مستقل از متن هم هست. زبان ها منظم زیر مجموعه همه زبان ها هستند پس زیر مجموعه زبان ها مستقل از متن هم هستند.

این زبان دوطرفش طول رشته محدود هست طول 2 هست پس براحتی میگیم منظمه و میشه براش ماشین FA کشید
منظم ها هم مستقل از متن هم هستند

(24 دى 1391 11:20 ب.ظ)dfsefes نوشته شده توسط: [ -> ]چطور هم منظمه و مستقل از متن؟
L={vwv: v,w{a,b}*, |v|=2} 93

ضمن تایید حرفای دوستان، اگه محدودیت روی طول v وجود نداشت، قضیه فرق می کرد.
البته باید توجه کرد که سوال، طرف راست و چپ رشته ای که توسط زبان پذیرفته میشه(دوعبارت از هر طرف) باید برابر و طول شون هم 2 باشه (یعنی مثلا *********** باید برابر باشند)، پس در این صورت گرامر بصورت :

[tex]S \rightarrow aaAaa|abAab|baAba|bbAbb[/tex]
[tex]A\rightarrow aA|bA|\varepsilon[/tex]



موفق باشید.

ممنون

V (وی) می تونه شامل {aa,ab,ba,bb} باشه که هر کاراکتر رو از ورودی گرفتیم میریزیم توی stack.
بعدش w میاد همه چیزو می گیره .
بعدش V باید تکرار بشه یعنی به ازای هر کاراکتر برداشت شده از پشته،معادلشو از ورودی پذیرش می کنیم.
===
پس PDA میشه براش رسم کرد میشه مستقل
--
ضمنا چون V طولش محدود (در اینجا 2 کاراکتر)هست میشه براش DFA یا ماشین حالت رسم کرد یا FSA .
پس منظم هم هست.
---
نکته : زبانی که منظم باشه حتما مستقل هم هست.
اما زبانی که مستقل هست ممکنه منظم نباشه.