870 views

2 Answers

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

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 , 

Related questions

0 votes
0 votes
2 answers
1
just_bhavana asked Jul 7, 2017
1,005 views
L = {ai bj ck | i = k or j = k}Is it a DCFL or an NCFL?
2 votes
2 votes
2 answers
2
Denson George asked Jan 10, 2017
1,556 views
L1={wlwR∣w∈{a,b}∗,l∈{a,b} }which type of language is this DCFL or NDCFL? (note that l∈{a,b} not {a,b}*)I feel its NDCFL can you also tell how PDA will look like...