Here is my homework for Automata Theory.
Pardon me for not being able to use MSPaint efficiently. ^^
As far as I can remember, the homework was to convert an NFA diagram to a DFA diagram.
Here's the NFA diagram:
Using subset construction, I am able to determine the states and state transitions.
δD({q0},a) = δN(q0,a) = {q1}
δD({q0},b) = δN(q0,b) = {q2}
δD({q1},a) = δN(q1,a) = {q3}
δD({q1},b) = δN(q1,b) = {}
δD({q2},a) = δN(q2,a) = {}
δD({q2},b) = δN(q2,b) = {q4}
δD({q3},a) = δN(q3,a) = {q3} U {q6} = {q3,q6}
δD({q3},b) = δN(q3,b) = {q3}
δD({q4},a) = δN(q4,a) = {q4} U {q6} = {q4,q6}
δD({q4},b) = δN(q4,b) = {q4}
δD({q3,q6},a) = δN(q3,a) ∪ δN(q6,a) = {q3,q6} ∪ {} = {q3,q6}
δD({q3,q6},b) = δN(q3,b) ∪ δN(q6,b) = {q3} ∪ {} = {q3}
δD({q4,q6},a) = δN(q4,a) ∪ δN(q6,a) = {q4,q6} ∪ {} = {q4,q6}
δD({q4,q6},b) = δN(q4,b) ∪ δN(q6,b) = {q4} ∪ {} = {q4}
δD({},a) = {}, δD({},b) = {}
From the subsets above we can produce this DFA:
However, we can still simplify the DFA (above). I'm not sure about the rules in simplifying DFAs yet, so I hope this will suffice for now:
Please leave your comments if I'm wrong or if I had broken some rules.
My Explanation On The Automata Assignment
J2ME RecordStore Example
import javax.microedition.midlet.*;
import javax.microedition.lcdui.*;
import javax.microedition.rms.RecordEnumeration;
import javax.microedition.rms.RecordStore;
import javax.microedition.rms.RecordStoreException;
/**
* Preferences Store
*
*Create a class that can persist program preferences. The class will store the preferences into a Record Store.
*Each record will have a variable name and value. Each variable/value pair is stored in a single record.
*The name and value are stored in the database as Strings.
*
*The class should implement these methods:
*public String readVar(RecordStore recStore, String name, String defaultValue)
*public void writeString(RecordStore recStore, String name, String value);
*
* @author calcifer
*
*/
public class PreferenceStore extends MIDlet implements CommandListener{
private Display display;
private Command exit;
private Command write;
private Command read;
private Command back;
private Form inputForm;
private TextBox output = new TextBox("Your Preference:", "", 250, TextField.ANY);
private TextField varName = new TextField("VarName:", "",32,TextField.ANY);
private TextField varValue = new TextField("Value:", "", 32,TextField.ANY);
private RecordStore recStore;
private Alert success;
public PreferenceStore(){
inputForm = new Form("Preference");
exit = new Command("Exit",Command.EXIT, 0);
write = new Command("Write", Command.OK, 0);
read = new Command("Read", Command.OK, 0);
back = new Command("Back", Command.BACK, 0);
output.addCommand(back);
output.setCommandListener(this);
inputForm.append(varName);
inputForm.append(varValue);
inputForm.addCommand(exit);
inputForm.addCommand(write);
inputForm.addCommand(read);
inputForm.setCommandListener(this);
success = new Alert("","Successfully Added!", null, AlertType.INFO);
}
public void startApp() {
try {
recStore = RecordStore.openRecordStore("Preferences", true);
} catch (RecordStoreException ex) {
ex.printStackTrace();
} catch (Exception e){
e.printStackTrace();
}
if(display == null){
display = Display.getDisplay(this);
}
display.setCurrent(inputForm);
}
public void pauseApp() {
}
public void destroyApp(boolean unconditional) {
}
public void commandAction(Command c, Displayable d){
if(c == exit){
notifyDestroyed();
try{
recStore.closeRecordStore();
}catch(Exception e){e.printStackTrace();}
}
else if(c == write){
display.setCurrent(success);
writeString(recStore, varName.getString(), varValue.getString());
varName.setString("");
varValue.setString("");
}
else if(c == read){
output.setString("");
output.setString(readVar(recStore, varName.getString(), varValue.getString()));
display.setCurrent(output);
varName.setString("");
varValue.setString("");
}
else if(c == back){
display.setCurrent(inputForm);
}
}
public void writeString(RecordStore recStore, String name, String value){
String newItem = new String(name + value);
byte[] bytes = newItem.getBytes();
try{
recStore.addRecord(bytes, 0, bytes.length);
}catch(Exception e){ e.printStackTrace();}
}
public String readVar(RecordStore recStore, String name, String defaultValue){
StringBuffer sb = new StringBuffer();
try{
RecordEnumeration enumerator = recStore.enumerateRecords(null, null, true);
while(enumerator.hasNextElement()){
String item = new String(enumerator.nextRecord());
String val = new String(name + defaultValue);
if(item.equals(val))
sb.append(item);
}
}catch(Exception e){e.printStackTrace();}
return sb.toString();
}
}
Interesting Computer Programming Quotes
I'm back! I have here some of the most interesting Computer Programming related quotes. Enjoy! ^^
Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to build bigger and better idiots. So far, the universe is winning.
* Rick Cook (or Rich Cook?) [citation needed]
The effective exploitation of his powers of abstraction must be regarded as one of the most vital activities of a competent programmer.
* Edsger W. Dijkstra, The Humble Programmer, 1972 Turing Award Lecture, Communications of the ACM 15 (10), (October 1972): pp. 859–866
There is no programming language, no matter how structured, that will prevent programmers from making bad programs.
* Larry Flon
No matter how slick the demo is in rehearsal, when you do it in front of a live audience the probability of a flawless presentation is inversely proportional to the number of people watching, raised to the power of the amount of money involved.
* Mark Gibbs
To me programming is more than an important practical art. It is also a gigantic undertaking in the foundations of knowledge.
* Grace Hopper, quoted in Management and the Computer of the Future (1962) by Sloan School of Management, p. 277
Premature optimization is the root of all evil.
* Donald Knuth, "Structured Programming with Goto Statements". Computing Surveys 6:4 (December 1974), pp. 261–301, §1.
Computer Science is embarrassed by the computer.
* Alan Perlis, "Epigrams on Programming"
Computer programmers never die, they just become lost in the processing.
* Anonymous
Computers can never replace human stupidity.
* Anonymous
Good programming is 99% sweat and 1% coffee.
* Anonymous
Read More ..
Fun Comic Strips
src: http://xkcd.com
Just click the comic strip to view a clearer image of it.
Enjoy! ^^
Game Theory
Qwertial Aphasia
Estimation
Cutting Edge
Extrapolating
Period
Increasing Virtual Memory In XP
I have posted here an easy and affordable tip to solve your 'low memory' problems in Windows XP.
To give you an overview, we are going to increase the system paging file size of your computer. System paging file is also called virtual memory. Virtual memory is part of a secondary memory that is used as if it were primary memory.
To increase the virtual memory of your computer, follow the steps below:
1) Go to 'System Properties' via the 'Control Panel' then click the 'Advanced' tab.
2) Inside the 'Performance Options' panel click the 'Settings' button.
3) Click the 'Advanced' tab then press the 'Change' button.
4) Select the disk volume you would like to use.
5) Set the 'Initial Size' and 'Maximum Size' according to your preference.
That's it, you're done. ^^
Note:
There are some OS's that automatically adjusts the virtual memory for you when you are encountering a 'low memory' problem.
Using The Mouse Pointer Without a Mouse
Do you have problems with your mouse? are you in such a rush that you do not have time to look for a spare and change it? or do you even have a spare?
Here is a handy tip for you.
Left Alt + Left Shift + Num Lock then OK.
This will activate the MouseKeys on your numpad so be sure the LED for NumLock is lit, otherwise it won't work.
The numbers 1,2,3,4,6,7,8 and 9 controls your pointer movement.
Use 5 for clicking. You can change from right-click to left-click through the /,* and - keys on the numpad.
The Pumping Lemma for Regular Languages
src: http://www.seas.upenn.edu/~cit596/notes/dave/pumping2.html
Here's what the pumping lemma says:
* If an infinite language is regular, it can be defined by a dfa.
* The dfa has some finite number of states (say, n).
* Since the language is infinite, some strings of the language must have length > n.
* For a string of length > n accepted by the dfa, the walk through the dfa must contain a cycle.
* Repeating the cycle an arbitrary number of times must yield another string accepted by the dfa.
The pumping lemma for regular languages is another way of proving that a given (infinite) language is not regular. (The pumping lemma cannot be used to prove that a given language is regular.)
The proof is always by contradiction. A brief outline of the technique is as follows:
* Assume the language L is regular.
* By the pigeonhole principle, any sufficiently long string in L must repeat some state in the dfa; thus, the walk contains a cycle.
* Show that repeating the cycle some number of times ("pumping" the cycle) yields a string that is not in L.
* Conclude that L is not regular.
Why this is hard:
* We don't know the dfa (if we did, the language would be regular!). Thus, we have do the proof for an arbitrary dfa that accepts L.
* Since we don't know the dfa, we certainly don't know the cycle.
Why we can sometimes pull it off:
* We get to choose the string (but it must be in L).
* We get to choose the the number of times to "pump."
Operations That Can Be Performed on Languages
Concatenation
L1 . L2 = L1L2 = {w ε Σ| w=xy for some x ε L1 and y ε L2}
Closure (pairing of elements)
examples:
L1 = {a}
L1* = {e,a,aa,aaa,aaaa,...}
L2 = {aa, bb}
L2* = {e,aa, bb,aaaa,aabb,bbaa,bbbb,...}
L3 = 0
L3* = {e}
(note: * is Kleene's Star and e represents empty)
Positive Closure Property
L+ = LL*
example:
L = {aa,bb}
L* = {e,aa,bb,aaaa,aabb,bbaa,bbbb,...}
L+ = {aa,bb,aaaa,aabb,bbaa,bbbb,...}
Elements of L are concatenated with the elements of L*.
Union
L = L1 ∪ L2
example:
L1 = {a}
L2 = {b}
L1 ∪ L2 = {a,b}
Intersection
L = L1 ∩ L2
example:
L1 = {a,b}
L2 = {b}
L1 ∩ L2 = {b}
Difference
L = L1 - L2
example:
L1 = {a,b}
L2 = {b}
L1 - L2 = {a}
Complement
~L = Σ* - L
OSI Layers
src:http://en.wikipedia.org/wiki/OSI_model
The Open Systems Interconnection Reference Model (OSI Reference Model or OSI Model) is an abstract description for layered communications and computer network protocol design.
A layer is a collection of conceptually similar functions that provide services to the layer above it and receives service from the layer below it. On each layer an instance provides services to the instances at the layer above and requests service from the layer below. For example, a layer that provides error-free communications across a network provides the path needed by applications above it, while it calls the next lower layer to send and receive packets that make up the contents of the path.
Short Description of OSI Layers (top to bottom)
Application Layer:
The layer that is closest to the end user. This layer interacts with software applications that implement a communicating component. Some examples of application layer implementations are Telnet, Hypertext Transfer Protocol (HTTP), File Transfer Protocol (FTP), and Simple Mail Transfer Protocol (SMTP).
Presentation Layer:
This layer provides independence from differences in data representation (e.g., encryption) by translating from application to network format, and vice versa. The presentation layer works to transform data into the form that the application layer can accept. This layer formats and encrypts data to be sent across a network, providing freedom from compatibility problems. It is sometimes called the syntax layer.
Session Layer:
It establishes, manages and terminates the connections between the local and remote application. It provides for full-duplex, half-duplex, or simplex operation, and establishes checkpointing, adjournment, termination, and restart procedures.
Transport Layer:
Provides transparent transfer of data between end users, providing reliable data transfer services to the upper layers. The Transport Layer controls the reliability of a given link through flow control, segmentation/desegmentation, and error control. Some protocols are state and connection oriented. This means that the Transport Layer can keep track of the segments and retransmit those that fail.
Network layer:
Provides the functional and procedural means of transferring variable length data sequences from a source to a destination via one or more networks, while maintaining the quality of service requested by the Transport Layer. The Network Layer performs network routing functions, and might also perform fragmentation and reassembly, and report delivery errors. Routers operate at this layer—sending data throughout the extended network and making the Internet possible. This is a logical addressing scheme – values are chosen by the network engineer. The addressing scheme is hierarchical.
Data Link Layer:
Provides the functional and procedural means to transfer data between network entities and to detect and possibly correct errors that may occur in the Physical Layer. Originally, this layer was intended for point-to-point and point-to-multipoint media, characteristic of wide area media in the telephone system.
Physical Layer:
The Physical Layer defines the electrical and mechanical specifications for devices.
Search Engine Tips
- Get to know your search engine if you haven't already discovered it (e.g. google, bing).
- To narrow down your internet search, enclose any search phrases in speech marks. eg: "Melbourne Observer". That way, you'll only get pages with the actual TERM 'Melbourne Observer' appearing. Without the speech marks, you'll get lots of pages with the word 'Melbourne', lots of pages with the term 'Observer', and then pages with the term 'Melbourne Observer'.
- Use a 'plus' sign with any words that MUST appear in the search results. Similarly, use a 'minus' sign with any words that MUST NOT appear in the search results. (There is no space between the symbol and the word) e.g.: "banana bread" +chocolate -sultanas
- When you come across a page that you will be visiting often, make sure you 'bookmark' it by adding it to your list of Favorites. With the page displayed, simply go up to the Favorites menu (yes, the US spelling!) and choose 'Add to Favorites'. If you are like me and you have an endless list, it would be a good idea to sort them into Folders, too.
- When you have done a search using a search engine like google and you're presented with a long list of pages you'd like to check out, this tip will help you do that without losing the original list: RIGHT MOUSE CLICK on the first link you'd like to open and choose from the shortcut menu that appears 'Open Link in New Window'. Some browsers have 'Open Link in New Tab', allowing you to view the contents of the link in the same browser having its own tab below the toolbars.
Read More ..
Automata Theory Part 2
Three Kinds of Finite Automata:
Deterministic Finite Automata (DFA)
Each state has a transition for every symbol in the alphabet.
Nondeterministic Finite Automata (NDFA)
States of an automaton of this kind may or may not have a transition for each symbol in the alphabet, or can even have multiple transitions for a symbol. The automaton accepts a word if there exists at least one path from q0 to a state in F labeled with the input word. If a transition is undefined, so that the automaton does not know how to keep on reading the input, the word is rejected.
Nondeterministic Finite Automata, with ε Transitions
Besides of being able to jump to more (or none) states with any symbol, these can jump on no symbol at all. That is, if a state has transitions labeled with ε, then the NFA can be in any of the states reached by the ε-transitions, directly or through other states with ε-transitions. The set of states that can be reached by this method from a state q, is called the ε-closure of q.
Automata Theory Part 1
Automata theory is actually the study of abstract machines and problems which they are able to solve. Automata theory is closely related to formal language theory as the automata are often classified by the class of formal languages they are able to recognize.An automaton is a mathematical model for a finite state machine (FSM). An FSM is a machine that, given an input of symbols, "jumps", or transitions, through a series of states according to a transition function (which can be expressed as a table).
The input is read symbol by symbol, until it is consumed completely. Once the input is depleted, the automaton is said to have stopped.
Depending on the state in which the automaton stops, the automaton either accepts or rejects the input (Final state or Dead state). If it landed in an accept state, then the automaton accepts the word. If, on the other hand, it lands on a reject state, the word is rejected. The set of all the words accepted by an automaton is called the language accepted by the automaton.
Automata play a major role in compiler design and parsing.
Vocabulary:
Symbol
An arbitrary datum which has some meaning to or effect on the machine.
Word
A finite string formed by the concatenation of a number of symbols.
Alphabet
A finite set of symbols. An alphabet is frequently denoted by Σ, which is the set of letters in an alphabet.
Language
A set of words, formed by symbols in a given alphabet. May or may not be infinite.
An automaton is represented by the 5-tuple
Read More ..
How to View Total and Free Memory in JAVA
This code snippet allows you to view the total memory and free memory in your console at runtime.public class MemoryViewing { public static void main(String[] args) { System.out.println("Total Memory: " + Runtime.getRuntime().totalMemory());System.out.println("Free Memory: " + Runtime.getRuntime().freeMemory()); }
}Runtime is a singleton.Genesis
Greetings!
I'll be posting in this blog about things you basically need to know about programming and computers. For simplicity I'll be using Java for OOP and C for other things.
I hope this helps and that you'll enjoy your visit.
