import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.Math;
public class Main {
public static void main(String[] args) {
ArrayList list = new ArrayList();
BufferedReader dataIn = new BufferedReader(new
InputStreamReader( System.in) );
//read current head position
String w = "";
System.out.println("Position of head currently :");
try{
w = dataIn.readLine();
}catch( IOException e ){
System.out.println("Error!");
}
int head = Integer.parseInt(w);
int initialhead = head;
// Read service requests
while(true){
try{
System.out.println("Enter next service request.Enter z to end the requests.");
w = dataIn.readLine();
if(w.equals("z"))
break;
int temp = Integer.parseInt(w);
list.add(temp);
}catch( IOException e ){
System.out.println("Error!");
}
}
ArrayList service_order = new ArrayList();//adds requests in order of the service
int number_of_orders = list.size();
for(int i=0; i <number_of_orders;i++){
Iterator it = list.iterator();
int min = 0;
int temp=0;
int min_distance=200;
while(it.hasNext()){
temp = (Integer)it.next();
int distance = Math.abs(head-temp);
System.out.println(head +" "+ temp+" " + distance );
if(distance < min_distance){
min = temp;
min_distance = distance;
}
}
list.remove((Integer)min);
head = min;
System.out.println(" Next request "+ min);
service_order.add(min);
}
Iterator min_it = service_order.iterator();
System.out.print("Service Order: ");
while(min_it.hasNext()){
System.out.print(min_it.next()+" ");
}
int total_head_movement=0;
min_it = service_order.iterator();
total_head_movement = Math.abs(initialhead - (Integer)service_order.get(0));
for(int i =1;i < service_order.size();i++){
total_head_movement += Math.abs((Integer)service_order.get(i) - (Integer)service_order.get(i-1));
}
System.out.println();
System.out.println("Total head movement: "+ total_head_movement);
}
}
Deepcopy of a string in c
Sunday, November 29, 2009
Tuesday, November 3, 2009
Process Synchronization Examples
The following Java code samples describe two Lock classes with two methods
each: acquire() and release(). You can assume that the application calls lock.acquire()
before entering a critical section and lock.release() after exiting the critical section. For the
implementations that require a tid (i.e., thread id), you can assume that the tid of each thread is
either 0 or 1.
For each lock, answer the following three questions. Be sure that your answers clearly indicate
whether you are referring to LockA or LockB.
(a) Does the code guarantee mutual exclusion? (Simply answer yes or no)
(b) Does the code guarantee progress? (Simply answer yes or no)
(c) List all other limitations that exist for each implementation. Issues you might consider
include (but are not limited to) the following: generality, efficiency, and fairness. (Note: You
can skip this part of the quetion when the implementation fails to provide mutual exclusion
or progress.)
Answer
LockA (a) Yes, guarantees mutual exclusion; only the thread with tid matching turn is able to
acquire the lock. (b) No, does not guarantee progress; if thread 0 never tries to acquire the lock
(it is executing other code), thread 1 will not be able to acquire the lock. (c) Limitations (Not
required): Only works with two processes, uses busy waiting.
LockB (a) Guarantees mutual exclusion on a uniprocessor, but not on a multiprocessor. On a
uniprocessor, once the timer interrupt is disabled, the scheduler won’t be able to switch to another
process (assuming the scheduled process doesn’t voluntarily relinquish the CPU). However, on
a multiprocessor, it is possible for the other CPU to be running a process that also acquires the
lock. (b) Yes, guarantees progress; once a process is scheduled, it is able to acquire the lock without
incident. (c) Limitations: Only works on uniprocessors; allows user processes to disable interrupts
for an arbitrary long period; cannot service other important interrupts during critical section (e.g.,
I/O); cannot schedule any other processes when lock is held, even those not contending for the
lock.
Also answer the following general question: Locks are often implemented by maintaining a list of processes (or threads) that are waiting to acquire the lock. What are all of the advantages of this approach (compared to a correct implementation of a lock that does not use a list)?
fairness and efficiency. Fairness comes from the fact that the queue can provide the lock to the
processes in the order they request it. Efficiency comes from the elimination of the spin lock, and
reliance on a notification mechanism to wake-up a process.
_______________________________________________________________
Suppose two processes compete for access to a critical section using simple spin locks. Prior to entering the critical section, the process executes the following:
while (TAS(t)); and after exiting the critical section it executes t=1.
(a) Suppose a priority scheduler where high priority processes always execute before any
lower priority processes. Can the described scheme lead to deadlock? If no, why not. If yes,
describe a case.
Yes, deadlock is possible. If a low priority process acquires the lock. Then a high priority
process starts, gets the processor and requests the lock. The high priority process will keep
the processor, spinning on the lock that the low priority process is holding. Because the low
priority process cannot get the processor, it cannot release the lock, and we have a deadlock
scenario.
(b) Suppose a round robin scheduler. Can the described scheme lead to deadlock? If no, why not. If yes, describe a case.
No, deadlock is not possible. A round robin, preemptive scheduler will alternate among
processes, so every process will have a chance to execute, and eventually the holding process
will release the lock.
_______________________________________________________________
Fix the following code to avoid the possible deadlock:
Answer
You could have changed this many ways. One possibility is to remove circular wait and
make both processes acquire the resources in the same order. Another possibility is to remove
hold-and-wait and have the processes release the first resource before they acquire another.
Although this changes the semantics of the program, I accepted it as a solution.
----------------------------------------------------------------------------------------------------------
Suppose a program has three threads Thread1, Thread2, and Thread3, and a
shared counter, count, as shown below:
int count = 10;
Semaphore Lock = 1; // initial value is 1
(a) What are the possible outputs of this program?
9, 10, 11
_______________________________________________________________________________________________
Consider a system with two preemptively scheduled threads. One thread executes the WriteA function
shown below. The other executes the WriteB function, also shown below. Both functions use kprintf
to produce console output. The random function called by WriteA returns a randomly-generated nonnegative
integer. WriteA and WriteB are synchronized using two semaphores, Sa and Sb. The intial
value of both semaphores is zero. Assume that the individual calls to kprintf are atomic.
a.
Consider the following 10-character console output prefixes. (Each prefix shows the first 10 characters
printed to the console.) Which of these prefixes could possibly be generated by the two
threads running in this system? Write “YES” next to the output prefix if it could be generated,
otherwise write “NO”.
• ABABABABAB YES
• BABABABABA NO
• AAAAAAAAAA YES
• AAABABABAB NO
• AAABBBBAAB NO
• AAAAAABBBB YES
• AAABBBAABB YES
• BBBBBAAAAB NO
b.
Suppose that the initial value of semaphore Sb is 1, rather than 0. Show a 10-character console
output prefix that could be generated in that case, and that could not be generated if the initial
value of Sb were 0.
Some examples:
• BABABABABA
• ABABBABABAB
• AAABBBABABB
__________________________________________________________________
Below is an attempted solution for producer- consumer problem. What problems can arise using this solution?
Buffer size = N
int count = 0;
Answer:
___________________________________________________________________________________
Consider three concurrently executing threads in the same process using two semaphores
s1 and s2. Assume s1 has been initialized to 1, while s2 has been initialized to 0.
What are the possible values of the global variable x, initialized to 0, after all three threads have terminated?
The possible sequences are B,C,A (x = 6) or C,A,B (x = 36) or C,B,A (x = 18).
________________________________________________________________
We explore the so-called barbershop problem. A barbershop consists of a n waiting chairs
and the barber chair. If there are no customers, the barber waits. If a customer enters,
and all the waiting chairs are occupied, then the customer leaves the shop. If the barber
is busy, but waiting chairs are available, then the customer sits in one of the free chairs.
Here is the skeleton of the code, without synchronization.
extern int N; /* initialized elsewhere to value > 0 */
int customers = 0;
void* customer() {
if (customers > N) {
return NULL;
}
customers += 1;
getHairCut();
customers -= 1;
return NULL;
}
void* barber() {
while(1) {
cutHair();
}
}
13
For the solution, we use three binary semaphores:
• mutex to control access to the global variable customers.
• customer to signal a customer is in the shop.
• barber to signal the barber is busy.
1. (5 points) Indicate the initial values for the three semaphores.
• mutex
• customer
• barber
2. (15 points) Complete the code above filling in as many copies of the following commands
as you need, but no other code.
P(&mutex);
V(&mutex);
P(&customer);
V(&customer);
P(&barber);
V(&barber);
Solution: Initial values are mutex = 1 (variable customers may
be accessed), customer = 0 (no customers) and barber = 0 (barber is not busy).
void* customer() {
P(&mutex);
if (customers > N) {
V(&mutex);
return NULL;
}
customers += 1;
V(&mutex);
V(&customer);
P(&barber);
getHairCut();
P(&mutex);
customers -= 1;
V(&mutex);
return NULL;
}
void* barber() {
while(1) {
P(&customer);
V(&barber);
cutHair();
}
}
________________________________________________________________
each: acquire() and release(). You can assume that the application calls lock.acquire()
before entering a critical section and lock.release() after exiting the critical section. For the
implementations that require a tid (i.e., thread id), you can assume that the tid of each thread is
either 0 or 1.
class LockA { private int turn = 0; public void acquire(int tid) { while (turn == (1 - tid)); } public void release(int tid) { turn = (1 - tid); } } | class LockB { public void acquire() { disableInterrupts(); } public void release() { enableInterrupts(); } } |
For each lock, answer the following three questions. Be sure that your answers clearly indicate
whether you are referring to LockA or LockB.
(a) Does the code guarantee mutual exclusion? (Simply answer yes or no)
(b) Does the code guarantee progress? (Simply answer yes or no)
(c) List all other limitations that exist for each implementation. Issues you might consider
include (but are not limited to) the following: generality, efficiency, and fairness. (Note: You
can skip this part of the quetion when the implementation fails to provide mutual exclusion
or progress.)
Answer
LockA (a) Yes, guarantees mutual exclusion; only the thread with tid matching turn is able to
acquire the lock. (b) No, does not guarantee progress; if thread 0 never tries to acquire the lock
(it is executing other code), thread 1 will not be able to acquire the lock. (c) Limitations (Not
required): Only works with two processes, uses busy waiting.
LockB (a) Guarantees mutual exclusion on a uniprocessor, but not on a multiprocessor. On a
uniprocessor, once the timer interrupt is disabled, the scheduler won’t be able to switch to another
process (assuming the scheduled process doesn’t voluntarily relinquish the CPU). However, on
a multiprocessor, it is possible for the other CPU to be running a process that also acquires the
lock. (b) Yes, guarantees progress; once a process is scheduled, it is able to acquire the lock without
incident. (c) Limitations: Only works on uniprocessors; allows user processes to disable interrupts
for an arbitrary long period; cannot service other important interrupts during critical section (e.g.,
I/O); cannot schedule any other processes when lock is held, even those not contending for the
lock.
Also answer the following general question: Locks are often implemented by maintaining a list of processes (or threads) that are waiting to acquire the lock. What are all of the advantages of this approach (compared to a correct implementation of a lock that does not use a list)?
fairness and efficiency. Fairness comes from the fact that the queue can provide the lock to the
processes in the order they request it. Efficiency comes from the elimination of the spin lock, and
reliance on a notification mechanism to wake-up a process.
_______________________________________________________________
Suppose two processes compete for access to a critical section using simple spin locks. Prior to entering the critical section, the process executes the following:
while (TAS(t)); and after exiting the critical section it executes t=1.
(a) Suppose a priority scheduler where high priority processes always execute before any
lower priority processes. Can the described scheme lead to deadlock? If no, why not. If yes,
describe a case.
Yes, deadlock is possible. If a low priority process acquires the lock. Then a high priority
process starts, gets the processor and requests the lock. The high priority process will keep
the processor, spinning on the lock that the low priority process is holding. Because the low
priority process cannot get the processor, it cannot release the lock, and we have a deadlock
scenario.
(b) Suppose a round robin scheduler. Can the described scheme lead to deadlock? If no, why not. If yes, describe a case.
No, deadlock is not possible. A round robin, preemptive scheduler will alternate among
processes, so every process will have a chance to execute, and eventually the holding process
will release the lock.
_______________________________________________________________
Fix the following code to avoid the possible deadlock:
| acquire(L1) acquire(L2) release(L2) release(L1) | acquire(L2) acquire(L1) release(L1) release(L2) |
You could have changed this many ways. One possibility is to remove circular wait and
make both processes acquire the resources in the same order. Another possibility is to remove
hold-and-wait and have the processes release the first resource before they acquire another.
Although this changes the semantics of the program, I accepted it as a solution.
----------------------------------------------------------------------------------------------------------
Suppose a program has three threads Thread1, Thread2, and Thread3, and a
shared counter, count, as shown below:
int count = 10;
Semaphore Lock = 1; // initial value is 1
| Thread1(...) { // do something Lock.Wait(); count++; Lock.Signal(); } | Thread2(...) { // do something Lock.Wait(); count−−; Lock.Signal(); } | Thread3(...) { // do something Lock.Wait(); printf(‘‘$d’’, count); Lock.Signal(); } |
9, 10, 11
_______________________________________________________________________________________________
Consider a system with two preemptively scheduled threads. One thread executes the WriteA function
shown below. The other executes the WriteB function, also shown below. Both functions use kprintf
to produce console output. The random function called by WriteA returns a randomly-generated nonnegative
integer. WriteA and WriteB are synchronized using two semaphores, Sa and Sb. The intial
value of both semaphores is zero. Assume that the individual calls to kprintf are atomic.
| WriteA() { unsigned int n,i; while(1) { n = random(); for(i=0;i<n;i++){ kprintf(‘‘A’’); } for(i=0;i<n;i++) { V(Sb); } for(i=0;i<n;i++) { P(Sa); } } | WriteB() { while(1) { P(Sb); kprintf(‘‘B’’); V(Sa); } } |
a.
Consider the following 10-character console output prefixes. (Each prefix shows the first 10 characters
printed to the console.) Which of these prefixes could possibly be generated by the two
threads running in this system? Write “YES” next to the output prefix if it could be generated,
otherwise write “NO”.
• ABABABABAB YES
• BABABABABA NO
• AAAAAAAAAA YES
• AAABABABAB NO
• AAABBBBAAB NO
• AAAAAABBBB YES
• AAABBBAABB YES
• BBBBBAAAAB NO
b.
Suppose that the initial value of semaphore Sb is 1, rather than 0. Show a 10-character console
output prefix that could be generated in that case, and that could not be generated if the initial
value of Sb were 0.
Some examples:
• BABABABABA
• ABABBABABAB
• AAABBBABABB
__________________________________________________________________
Below is an attempted solution for producer- consumer problem. What problems can arise using this solution?
Buffer size = N
int count = 0;
| consumer: while(true){ if(count==0) sleep( ); //remove from buffer count--; if(count ==N-1) wakeup(producer); consume(item) } | producer: while(true){ produce(item); if(count==N) sleep( ); //produce into buffer count++; if(count ==1) wakeup(consumer); consume(item) } |
Answer:
- Consumer checks count==0
- before going to sleep consumer is preempted
- Producer increments count to 1
- producer wakes up consumer.
- since consumer is not sleeping yet, wakeup call is lost.
- Producer fills the buffers until count == N and goes to sleep
- Both processes are deadlocked.
___________________________________________________________________________________
Consider three concurrently executing threads in the same process using two semaphores
s1 and s2. Assume s1 has been initialized to 1, while s2 has been initialized to 0.
What are the possible values of the global variable x, initialized to 0, after all three threads have terminated?
/* thread A */ P(&s2); P(&s1); x = x*2; V(&s1); | /* thread B */ P(&s1); x = x*x; V(&s1); | /* thread C */ P(&s1); x = x+3; V(&s2); V(&s1); |
The possible sequences are B,C,A (x = 6) or C,A,B (x = 36) or C,B,A (x = 18).
________________________________________________________________
We explore the so-called barbershop problem. A barbershop consists of a n waiting chairs
and the barber chair. If there are no customers, the barber waits. If a customer enters,
and all the waiting chairs are occupied, then the customer leaves the shop. If the barber
is busy, but waiting chairs are available, then the customer sits in one of the free chairs.
Here is the skeleton of the code, without synchronization.
extern int N; /* initialized elsewhere to value > 0 */
int customers = 0;
void* customer() {
if (customers > N) {
return NULL;
}
customers += 1;
getHairCut();
customers -= 1;
return NULL;
}
void* barber() {
while(1) {
cutHair();
}
}
13
For the solution, we use three binary semaphores:
• mutex to control access to the global variable customers.
• customer to signal a customer is in the shop.
• barber to signal the barber is busy.
1. (5 points) Indicate the initial values for the three semaphores.
• mutex
• customer
• barber
2. (15 points) Complete the code above filling in as many copies of the following commands
as you need, but no other code.
P(&mutex);
V(&mutex);
P(&customer);
V(&customer);
P(&barber);
V(&barber);
Solution: Initial values are mutex = 1 (variable customers may
be accessed), customer = 0 (no customers) and barber = 0 (barber is not busy).
void* customer() {
P(&mutex);
if (customers > N) {
V(&mutex);
return NULL;
}
customers += 1;
V(&mutex);
V(&customer);
P(&barber);
getHairCut();
P(&mutex);
customers -= 1;
V(&mutex);
return NULL;
}
void* barber() {
while(1) {
P(&customer);
V(&barber);
cutHair();
}
}
________________________________________________________________
Tasks T1 and T2 share the integer variables X, Y initially set to
0.
Task T1 executes: | and T2 executes:
|
X := 0; | Y := 0;
if X > 0 then | while Y < 2 do
X := X + 1; | X := X - 1;
Y := 2; | Y := 1;
What are the possible values of X and Y when these tasks
terminate?
T1:1 X=0
T2:1 y=0
T2:2 x=-1
T1:3 Y=2
T2:2 Y=1
X =-1; Y=1 -----CONSIDER ALL POSSIBILITIES LIKE THESE EXAMPLES
______________________________________________________________________________
Process P executes:
A1: X := 1;
A2: Y := 1;
A3: Z := 2;
and process Q executes:
B1: X := 2;
B2: Y := 2;
What are the possible resulting values for X, Y, and Z?
For example, after the execution sequence A1 A2 A3 B1 B2
we obtain [x=2,y=2,z=2].
B1 A1 B2 A2 A3[x=1, y=1,Z=2]
try all combinations
In the same conditions as above, what should you do if you want
to guaranty that X, Y, Z finish with value, respectively, 1,
2, and 2?
You can change the order of A1, A2, A3; or the order of B1, B2;
or use semaphores; or use spinlocks.
Answer:
semaphore sem =0;
P1: P2
wait(sem) x=2
x=1 signal(sem)
y=1 wait(sem)
signal(sem) y=2
Z=2
In the same conditions as above, what should you do if you want
that X and Y have both value 1 or both value 2?
For both x=1 and y=1
semaphore sem =0;
P1: P2:
wait(sem)
x=1 x=2
y=1 y=2
Z=2 signal(sem)
______________________________________________________________________________
http://pages.cs.wisc.edu/~bart/537/quizzes/quiz1.html
______________________________________________________________________________
Monday, November 2, 2009
Pumping Lemma Examples
Steps to solve Pumping Lemma problems:
1. If the language is finite, it is regular , otherwise it might be non-regular.
2. Consider the given language to be regular
3. State pumping lemma
4. Choose a string w from language, choose smartly .
5. Partition it according to constraints of pumping lemma in a generic way
6. Choose a pumping factor k such that the new ‘pumped’ string is not part of the language
given.
7. State the contradiction and end the proof.
How to remember what pumping Lemma says:
Pumping Lemma alternates between “for all” and “there is at least one” or “for every” or
“there exists”. Notice:
For every regular language L
There exists a constant n
For every string w in L such that |w| >= n,
There exists a way to break up w into three strings w = xyz such that |y| > 0 , |xy| <= n and For every k>=0 , the string xykz is also in L.
courtesey: http://suraj.lums.edu.pk/~cs311w05/pumping_lemma_writeup.pdf
1. Show that L2 = {0m1m | x ∈ {0, 1}*} is not regular.
We show that the pumping lemma does not hold for L1. Consider any pumping number p; p≥ 1. Choose w = 0p1p.
Consider any pumping decomposition w = xyz;
|y| > 0 and |xy| ≤ p. It follows that x = 0a and y = 0b and z = 0p-a-b1p, for b ≥ 1. Choose i = 2. We need to show that xy2z = 0p+b1p is not in L1.
b ≥ 1.
So p+b > p
Hence 0p+b1p is not in L.
2. L2 = {xx | x ∈ {0, 1}*} is not regular.
We show that the pumping lemma does not hold for L2. Consider any pumping number
p ≥ 1. Choose w = 10p10p. Consider any pumping decomposition w = xyz; all we know about xyz is that
|y| > 0 and |xy| ≤ p. There are two possibilities:
(a) x = 10aand y = 0b and z = 0p-a-b10p, for b ≥ 1.
(a) x = " and y = 10b and z = 0p-b10p1.
Choose i = 2. We need to show that xy2z is not in L2.
In case (a), xy2z = 10p+b10p, which is not in L2 because b ≥ 1.
In case (b), xy2z = 10b10p10p, which is not in L2 because it contains three 1’s.
3. We prove that L3 = {1n2 | n ≥ 0} is not regular.
We show that the pumping lemma does not hold for L3. Consider any pumping number p ≥ 1.
Choose w = 1p2.
Consider any pumping decomposition w = xyz such that |y| > 0 and |xy| ≤ p. It follows
that x = 1a and y = 1b and z = 1p2
−a−b, for b ≥ 1 and a + b ≤ p. Choose i = 2. We need to show that
xy2z = 1n2+b is not in L3; that is, we need to show that p2 + b is not a square. Since b ≥ 1, we have
p2 + b > p2. Since a + b ≤ p, we have p2 + b ≤ p2 + p < (p + 1)2 4.Prove that Language L = {0n: n is a perfect square} is irregular.
Solution: L is infinite. Suppose L is also regular. Then according to pumping lemma there exists an integer n such that for every string w in where |w| >= n, we can break w into three strings w = xyz such that:
|y| > 0 , |xy| <= n and for all k>=0 , the string xykz is also in L.
Choose w to be w = 0s where s = n2 that is it is a perfect square.
Let w= 00000000000000000………00000 = xyz . (The length of w = s = n2 in this case.)
Let |xy| <= n and |y| = k. That is w = 0000 0k 000… X y z So, |xyz| = |xz| + |y| = (n2- k ) + (k) From pumping lemma, I can pump y any number of times and the new string should also belong to the language. Suppose I pump y twice then, the new string should belong to the language that is it should have length that is a perfect square but, |xy2z| = |xz| + 2|y| = (n2- k ) + 2k = n2 + k where n2 + k < 1 =" (n+1)(n+1)"> n2 (As k > 0)
=> n2 <>2 + k < (n+1)2 => n2 + k is not a perfect square
=> xy2z is not in L
=> This is a contradiction to the pumping lemma
So, our initial assumption must have been wrong that is L is not regular.
1. If the language is finite, it is regular , otherwise it might be non-regular.
2. Consider the given language to be regular
3. State pumping lemma
4. Choose a string w from language, choose smartly .
5. Partition it according to constraints of pumping lemma in a generic way
6. Choose a pumping factor k such that the new ‘pumped’ string is not part of the language
given.
7. State the contradiction and end the proof.
How to remember what pumping Lemma says:
Pumping Lemma alternates between “for all” and “there is at least one” or “for every” or
“there exists”. Notice:
For every regular language L
There exists a constant n
For every string w in L such that |w| >= n,
There exists a way to break up w into three strings w = xyz such that |y| > 0 , |xy| <= n and For every k>=0 , the string xykz is also in L.
courtesey: http://suraj.lums.edu.pk/~cs311w05/pumping_lemma_writeup.pdf
1. Show that L2 = {0m1m | x ∈ {0, 1}*} is not regular.
We show that the pumping lemma does not hold for L1. Consider any pumping number p; p≥ 1. Choose w = 0p1p.
Consider any pumping decomposition w = xyz;
|y| > 0 and |xy| ≤ p. It follows that x = 0a and y = 0b and z = 0p-a-b1p, for b ≥ 1. Choose i = 2. We need to show that xy2z = 0p+b1p is not in L1.
b ≥ 1.
So p+b > p
Hence 0p+b1p is not in L.
2. L2 = {xx | x ∈ {0, 1}*} is not regular.
We show that the pumping lemma does not hold for L2. Consider any pumping number
p ≥ 1. Choose w = 10p10p. Consider any pumping decomposition w = xyz; all we know about xyz is that
|y| > 0 and |xy| ≤ p. There are two possibilities:
(a) x = 10aand y = 0b and z = 0p-a-b10p, for b ≥ 1.
(a) x = " and y = 10b and z = 0p-b10p1.
Choose i = 2. We need to show that xy2z is not in L2.
In case (a), xy2z = 10p+b10p, which is not in L2 because b ≥ 1.
In case (b), xy2z = 10b10p10p, which is not in L2 because it contains three 1’s.
3. We prove that L3 = {1n2 | n ≥ 0} is not regular.
We show that the pumping lemma does not hold for L3. Consider any pumping number p ≥ 1.
Choose w = 1p2.
Consider any pumping decomposition w = xyz such that |y| > 0 and |xy| ≤ p. It follows
that x = 1a and y = 1b and z = 1p2
−a−b, for b ≥ 1 and a + b ≤ p. Choose i = 2. We need to show that
xy2z = 1n2+b is not in L3; that is, we need to show that p2 + b is not a square. Since b ≥ 1, we have
p2 + b > p2. Since a + b ≤ p, we have p2 + b ≤ p2 + p < (p + 1)2 4.Prove that Language L = {0n: n is a perfect square} is irregular.
Solution: L is infinite. Suppose L is also regular. Then according to pumping lemma there exists an integer n such that for every string w in where |w| >= n, we can break w into three strings w = xyz such that:
|y| > 0 , |xy| <= n and for all k>=0 , the string xykz is also in L.
Choose w to be w = 0s where s = n2 that is it is a perfect square.
Let w= 00000000000000000………00000 = xyz . (The length of w = s = n2 in this case.)
Let |xy| <= n and |y| = k. That is w = 0000 0k 000… X y z So, |xyz| = |xz| + |y| = (n2- k ) + (k) From pumping lemma, I can pump y any number of times and the new string should also belong to the language. Suppose I pump y twice then, the new string should belong to the language that is it should have length that is a perfect square but, |xy2z| = |xz| + 2|y| = (n2- k ) + 2k = n2 + k where n2 + k < 1 =" (n+1)(n+1)"> n2 (As k > 0)
=> n2 <>2 + k < (n+1)2 => n2 + k is not a perfect square
=> xy2z is not in L
=> This is a contradiction to the pumping lemma
So, our initial assumption must have been wrong that is L is not regular.
Subscribe to:
Posts (Atom)