+1 vote
247 views

yes. It is CFL and not DCFL. Only if some separating character like 'c' is at the middle it will be DCFL.

Palindrome mean that can be even palindrome or that can be odd palindrome

In even palindrome say L = w wr where we need to give a transition (in between with the help of ) after which we know reverse get started.

L= w ∊ wr     [eq: ababbaba as ababbaba ]

before ∊ we need to push symbols in stack , after∊we need to pop symbol from stack

PUSH operation

$\delta$(q,a,Z) =$\delta$(q, aZ)
$\delta$(q,b,Z) =$\delta$(q, bZ)
$\delta$(q,a,a) =$\delta$(q, aa)
$\delta$(q,b,b) =$\delta$(q, bb)
$\delta$(q,a,b) =$\delta$(q, ab)

$\delta$(q,b,a) =$\delta$(q, ba)

then DONOTHING

$\delta$(q,,a )= (q1,a)

$\delta$(q,,b )= (q1,b)    [State change with  , a Mark now we will get wr, so we need to do POP]

then POP operations

$\delta$(q1,a,a) = (q1, )

$\delta$(q1,b,b)= (q1,)

Then acceptance
$\delta$(q1,∊,Z) = (qf ,∊)

So Palindrome is NCFL

Note: we talk about L= { wcwr  | w∊ (a,b)*  } that is DCFL ,

2
+1 vote