Skip to main content
kiwicomb123's user avatar
kiwicomb123's user avatar
kiwicomb123's user avatar
kiwicomb123
  • Member for 10 years, 10 months
  • Last seen more than a month ago
  • Canada
comment
Why is the start symbol "not allowed" on the right hand side in Chomsky normal form?
This is better than most textbook answers, however I do not believe it answers the question. You have stated that it is sometimes useful to have the property w != empty_string and that some proofs of the pumping lemma use this property. However why is that important? All we are trying to do is put the grammar into Chomsky Normal Form. The question says nothing about trying to prove the pumping lemma.
comment
Show that a language consisting of strings of a prime number of 1s is irregular using pumping lemma
p(1+s) is not prime because it is divisible by p. By definition prime numbers are only divisible by 1 or themselves. Since p != p(1+s) and p(1+s) is certainly divisible by p, we can conclude that p(1+s) is not prime.
awarded