Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged pumping
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
401
views
Abhisek Mukherjee
asked
Nov 14, 2017
Theory of Computation
theory-of-computation
pumping-lemma
regular-language
pumping
lemma
+
–
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
502
views
rahul sharma 5
asked
Jan 11, 2017
Theory of Computation
theory-of-computation
pumping-lemma
pumping
lemma
+
–
0
votes
1
answer
3
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
427
views
vivek9837
asked
Oct 8, 2016
Theory of Computation
pumping
lemma
theory-of-computation
+
–
To see more, click for the
full list of questions
or
popular tags
.
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register