Explain how an unrestricted grammar can be defined as a super set of CFG and regular grammar?

we use a theorem to verify this statement.

theorem X-:every context free language is decidable=above superset conditions etc

let us consider that A is a CFL.

We want to show that A is decidable.

One idea is to conver PDA of A into TM….PDA of A can be Non Deterministic…or whatever…we can convert to turing legally…

as in non determinism…some branches of our PDA may have¬† non deterministic state transformation¬† and go upto infinity…so it is diffcult…in that process….



proof of theorem X-:

Let us take a CFG for A…..and name it as G……..

now let’s draw a turing machine for G i…TMg…

we need to prove that cfg is decidable…and we have cfg G…so it becomes the duty of Turing Machine to decide it…

so…its working will be as follows-:

TMg on i/p w—

Step 1: PROCESS the ip like the computer….

Step 2:If machine accepts…accept..else vice versa..

the theorem X provides us with the relationship of fourm main classes of language…though we need to know about only three…CFG, regular grammer.



Be the first to comment

Leave a Reply

Your email address will not be published.