My Computer Forum Computer Science Forum

Go Back   My Computer Forum > Computer Science Forum > Theory of Computation

Theory of Computation Theoretical Computer Science - Automata Theory, Computability Theory, and Computational Complexity Theory


Reply
 
LinkBack Thread Tools Display Modes
January 5th, 2012, 09: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!
kellyk is offline  
 

My Computer Forum is free to register and we welcome everyone!

April 29th, 2012, 09:58 PM   #2
 
Joined: Apr 2012
Posts: 4
Re: proving regular languages - i have a hard one!

i can't do this!!!!
andyou111 is offline  
Reply

  My Computer Forum > Computer Science Forum > Theory of Computation

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 06:27 PM
hard drive to USB musicworld1 Computer Science 4 January 2nd, 2013 01:45 PM
Want Help to Buy a New hard drive Imanuel4u Networking 6 August 22nd, 2011 11:27 PM
Regular Language ajitjjn Theory of Computation 0 December 6th, 2010 08:18 AM
hard to turn off winttery Networking 5 July 28th, 2010 12:19 AM





Copyright © 2018 My Computer Forum Forum. All rights reserved.