1. (a) Kweli, kwa kuwa kila lugha ya kawaida haina muktadha, kila lugha isiyo na muktadha inaweza kuamuliwa, na kila lugha inayoweza kuamuliwa inaweza kutambulika.
Kwa nini lugha zisizo na muktadha zinaweza kuamuliwa?
Tatizo lisiloweza kuamuliwa halina algoriti ya kubainisha jibu la ingizo fulani Utata wa lugha zisizo na muktadha: Kwa kuzingatia lugha isiyo na muktadha, hakuna mashine ya Turing ambayo itafanya. simamisha kila wakati kwa muda na utoe jibu kama lugha ina utata au la.
Je, sehemu ndogo ya lugha isiyo na muktadha inaweza kuamuliwa?
2 Majibu. Σ haina muktadha (hakika, ni ya kawaida) na ina vijisehemu vingi vidogo. Ikiwa L ni lugha isiyo na muktadha ya saizi isiyo na kipimo, basi kuna sehemu ndogo za J ya L ambazo zinaweza kuamuliwa, na zingine ambazo haziwezi kuamuliwa. Kwa mfano, kitengo kidogo tupu kinaweza kuamuliwa.
Je, CFL inaweza kuamua?
CFL: Inaweza inaweza kuamuliwa kwa tatizo la utupu, tatizo la ukomo, na tatizo la uanachama.
Ni lugha ngapi hazina muktadha?
(1) Kuna idadi isiyo na kikomo ya lugha zisizo na muktadha. Hii ni kweli kwa sababu kila maelezo ya lugha isiyo na muktadha yana urefu usio na kikomo, kwa hivyo kuna idadi isiyo na kikomo ya maelezo kama haya. (2) Kuna idadi isiyohesabika ya lugha.
