Recent questions tagged lemma / GATE Overflow for GATE CSE

2 votes

1 answer

1

Pumping Lemma problem
0^3m over the alphabets {0,1} , m E I+ is a regular language right? We can draw the DFA for it. Which means it cannot be tested using pumping lemma for regularity, but since we already know it is regular, whenever we take any string generated by L ... the pumping lemma constrains , so that on pumping, we have 0^(3p+1) , not acceptable by the machine. Where have I messed up?

0^3m over the alphabets {0,1} , m E I+ is a regular language right? We can draw the DFA for it.Which means it cannot be tested using pumping lemma for regularity, but sin...

Abhisek Mukherjee

411 views

Abhisek Mukherjee asked Nov 14, 2017

0 votes

0 answers

2

TOC Pumping Lemma
In pumping lemma it says if there is a string whose length is >=N,where N is number of states in dfa,then language of machine is infinite,but there is one upper constraing also. 2N-1>=|W|>=N Can anyone tell me about the use of 2N-1 here ?

In pumping lemma it says if there is a string whose length is >=N,where N is number of states in dfa,then language of machine is infinite,but there is one upper constrain...

rahul sharma 5

515 views

rahul sharma 5 asked Jan 11, 2017

4 votes

2 answers

3

Pumping Lemma

monty

2.5k views

monty asked Oct 28, 2016

0 votes

1 answer

4

Pumping lemma for CFG in alternative normal form
Let us say that a CFG is given in the following normal form where every production is of either type Non-terminal →Non-terminal Non-terminal Non-terminal Non-terminal → single-terminal Following is a CFG in the above normal form S→XYZ X→SXY ... by a CFG in the above normal form to guarantee a self-embedded non-terminal in any derivation of the word w

Let us say that a CFG is given in the following normal form where every production is of either typeNon-terminal →Non-terminal Non-terminal Non-terminalNon-terminal →...

vivek9837

449 views

vivek9837 asked Oct 8, 2016

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