
Theory of Computation Theoretical Computer Science  Automata Theory, Computability Theory, and Computational Complexity Theory 
 LinkBack  Thread Tools  Display Modes 
January 5th, 2012, 08:31 PM  #1 
Joined: Jan 2012 Posts: 1  proving regular languages  i have a hard one!
This is out of the sipser book, introduction to theory of computation. I don't even need to do this exercise but when I saw it, it had me confused! The question is this: a) Let B = {1^ky y is a string in alphabet {0,1}* and y contains at least k 1s, for k => 1} Show that B is a regular language b) Let C = {1^ky y is a string in alphabet {0,1}* and y contains at most k 1s, for k => 1} Show that C isnt a regular language In case my writing didnt make any sense, the string is 1^ky, meaning there is k amount of 1s at the start, and a string y follows that, where within that string y, it contains at least k amount of 1's (well thast question a, question b is at most k amount of 1s). My question is, HOW is a) regular? Its impossible to be regular! 
My Computer Forum is free to register and we welcome everyone! 
April 29th, 2012, 08:58 PM  #2 
Joined: Apr 2012 Posts: 4  Re: proving regular languages  i have a hard one!
i can't do this!!!!


Tags 
hard, languages, proving, regular 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Hard Drive Partition  aluya  Computer Storage  0  November 13th, 2013 05:27 PM 
hard drive to USB  musicworld1  Computer Science  4  January 2nd, 2013 12:45 PM 
Want Help to Buy a New hard drive  Imanuel4u  Networking  6  August 22nd, 2011 10:27 PM 
Regular Language  ajitjjn  Theory of Computation  0  December 6th, 2010 07:18 AM 
hard to turn off  winttery  Networking  5  July 27th, 2010 11:19 PM 