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….

SO WE NEED A DIFFERENT IDEA

**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.

## Leave a Reply