automata - Is the following language context free grammar? -


for n>=0, given grammar (a^na^na^n) context free? tried using pumping lemma, , result was, no not context free.

for pumping lemma work need show, can find word , "pump up" in order break rules of pl.

in case have a^n a^n a^n , want split words word uv^kw still in specified grammar.

in case not work!

to see have think several cases:

1) u @ least 1 (as v cant empty definition of pl), making v , w rest of a's

2) u has lenght a^n, v has length of @ least a^n , w has length of a^n

3) ...

imagine have stencil of length k , put under every imaginable position of a^n a^n a^n so:

pumping lemma

if add 1 n, resulting word wont anymore in a^n a^n a^n, therefore pl fails. language a^n a^n a^n equals a^n b^n c^n standard example failing pl.

sidenote: if pl not fail cant conclude grammar context-free. pl works 1 direction.


Comments

Post a Comment

Popular posts from this blog

How to group boxplot outliers in gnuplot -

i have large set of data points. try plot them boxplot, of outliers exact same value , represented on line beside each other. found how set horizontal distance between outliers in gnuplot boxplot , doesn't much, apparently not possible. is possible group outliers together, print 1 point , print number in brackets beside indicate how many points there are? think make more readable in graph. for information, have 3 boxplots 1 x value , times 6 in 1 graph. using gnuplot 5 , played around pointsize, doesn't reduce distance anymore. hope can help! edit: set terminal pdf set output 'dat.pdf' file0 = 'dat1.dat' file1 = 'dat2.dat' file2 = 'dat3.dat' set pointsize 0.2 set notitle set xlabel 'x' set ylabel 'y' header = system('head -1 '.file0); n = words(header) set xtics ('' 1) set [i=1:n] xtics add (word(header, i) i) set style data boxplot plot file0 using (1-0.25):1:(0.2) boxplot lw 2 lc rgb '#8b0000...
Read more

cakephp - simple blog with croogo -

i not problem, made simple blog in croogo, problem is not adding or modifying or delete, because arabic language ?? function add in controller `public function admin_add() { $this->set('title_for_layout', __('add part')); if (!empty($this->request->data)) { $this->part->create(); if ($this->part->save($this->request->data)) { $this->session->setflash(__('the part has been saved'), 'default', array('class' => 'success')); $this->redirect(array('action' => 'index'));//, $this->part->id)); } else { $this->session->setflash(__('the part not saved. please, try again.'), 'default', array('class' => 'error')); } } }` => model `class part extends appmodel { public $name = 'part'; var $belongst...
Read more