The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote
asked in Theory of Computation by (345 points) | 205 views

2 Answers

+2 votes
yes. It is CFL and not DCFL. Only if some separating character like 'c' is at the middle it will be DCFL.
answered by Boss (18k points)
+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)


 $\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 , 

answered by Veteran (54.5k points)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

35,499 questions
42,765 answers
42,150 users