Introduction.
Week 2 Exercises .
The aim of this exercise is to review the use of threads in Java. This will be done in the context of strings matching . You will be asked to answer a few questions related to this subject and to write a java program that illustrate the concepts mentioned.
More precisely you will be asked to write a program that answer yes or no if a given string belong to a given formal language. If you need to review how to use threads in Java you can go to the following link
https://docs.oracle.com/javase/tutorial/essential/concurrency/runthread.html
Problem 1.
The alphabet of the language is made of the letters “a” and “b” or if you prefer to use a more standart notation Σ = 𝑎, 𝑏 . The language L define on this alphabet is made of all strings that contain any number of “a” and an odd number of “b”.
Examples: aab ∈ L (there is only one b i.e. an odd number)
aabb ∉ L ( we have here an even number of b’s)
b ∈ L ( any number of a’s including 0 and an odd number of b’s)
These notions play a central role in the design of computer languages and the design of compilers and interpreters. One of the very basic question to ask: given a string does it belong to the defined language.
Q1.Write a Java program that can take as input any strings built with the alphabet described above and answer yes or no if that string belongs to the language L.
Q2. Write a threaded version of your program You should be able to read different strings from a file and assign each one to a thread. Do you notice any particularity of the output between the two programs. What are the advantages and desavantages if any of using threads in programming.
Problem 2.
In this problem we want to find a word, an expression in a text. To keep things simple again we will consider a very simple alphabet to built our words ∑ = ⎨ a,b,c⎬ and this time the language is made of all the stings that contain aab as a substing.
Write a threaded program to determine if a given word belongs to that language. Verify your program using the following input .
ccababccbcabaaccabaabccbcaacaa cab
accbaa
cccaabacaab ababababababababbbabaab
ccb
adaab
ccabaabccbcaabaa ccababccbcabaaccabaabccbcaacaa
Q1. Describe the alogrithm you have used to identify the legal words.
Q2. What is the complexity of your algorithm ?
Q3. Do you think your algorithm is the most efficient approach to this problem. Justify your
answer.
Note: If you are not familiar with strings algorithms , read the article String Algorithms by
Jaehyun Park
Problem 3
Q1. What is Java RMI what is it used for?
Q2. Describe CORBA and its principal characteristics .
Q3. Compare Java RMI and Corba particularly when to use them.
END