Pumping Lemma

input please

Page 1 of 1

0 Replies - 1116 Views - Last Post: 09 October 2009 - 04:17 AM

#1 handle   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 14
  • Joined: 01-February 09

Pumping Lemma

Posted 09 October 2009 - 04:17 AM

Just wondering if this makes sense, I kinda think I made some mistakes.

for a Language L = {wtw| w, t ε {0,1}*} prove that this is not regular.

my line of thought:

let w = 0^p 1, and let t = ε(empty set), then a string s = wtw = (0^p 1)(0^p 1) ε L
since |s| > p, s can be written as s = xyz. Because |xy| <= p, xy must equal 0^p, and therefore z is equal to 1 0^p 1. xyyz however, does not exist in L, and therefore L is not regular.

Is This A Good Question/Topic? 0
  • +

Page 1 of 1