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.