Polya Problem

Test 3, question 1.

The question described the machine that accepts odd length strings with a number of 1's that is 2 mod 3 (when divided by three has a remainder of 2). The first part of the question asked us to define, without proof, the state invariants and the second part asked us to give the state of the machine for a given extended transition function.

Step 1, understanding the problem:
The first part of the question asked us to define the states of the machine. For this part of the question I needed to understand the individual machines whose intersection formed the machine in the question. I then needed to find the Cartesian product of the two machines to get their intersection. Finally I needed to understand the transition functions of each machine, specifically which state they went to after seeing a certain input at a certain state. With these I thought I could describe the state transitions for the first part of the question and then use these to solve the second part of the question.

Step 2, devising a plan:
Since I had seen a similar problem on the third assignment, the machine that accepts odd length strings divisible by 5, I initially decided to approach the problem in a similar manner. Since the problem gave the transition of each state on a given input, I decided to use the one state invariant the question had given us to figure out the other 5. Once I had gotten the state invariants, I could use this information to determine the state of the machine for a given extended transition function for the second part of the question.

Step 3, implementing the plan:
I started by drawing out the individual machines. The machine for accepting odd length strings was simple enough, it had two states with a starting state for even length strings that transitioned on a 1 or a 0 to the accepting odd length string state and that transitioned back on a 1 or 0 to the even length state. The machine that accepts strings with a number of 1's that is 2 mod 3, was more complicated but the concept was similar. The question gave us the state invariant that was (q0, q'0)=an even number of zero's and a number of 1's such that 0 mod 3, using the two machines and this invariant I found that the other invariants were:
(q0, q'1)=an even number of zero's and a number of 1's such that 1 mod 3,
(q0, q'2)=an even number of zero's and a number of 1's such that 2 mod 3,
(q1, q'0)=an odd number of zero's and a number of 1's such that 0 mod 3,
(q1, q'1)=an odd number of zero's and a number of 1's such that 1 mod 3,
(q1, q'2)=an odd number of zero's and a number of 1's such that 2 mod 3,

For the second part of the question, I used the previous states to determine the state the extended transition would lead to. For example the state
d*(S,100100) has an even number of 0's and 2 1's, which when divided by 3 has remainder 2. Thus it is in state q0,q'2.

Conclusion: Overall I found that I was able to effectively apply my past experiences from assignment 3 to help me with this question. I was satisfied with the way I solved this problem and I think my method was the most efficient way to approach the problem.

Overall thoughts on csc236

We just had our final lecture in csc236 and have finished wrapping up the loose ends of the course material. With only one test left and then the exam, it's safe to say were basically finished the course. In many ways I greatly enjoyed csc236 more than most of the courses i've taken so far. The course material was interesting and I thought that the lectures were properly allocated to effectively cover the required material. I found the lectures to be extremely informative, especially because of how we went through examples together, and an effective way to learn the material. I surprisingly liked the weekly problem sets and thought they were a good way to keep ontop of the material. I also started using the help center and went to office hours more often (Heap center?), both of which I found to be of great help when I got stuck on certain points of the assignment. If there were areas to improve the course I'd suggest for next year, I'd like to see more of how some of the concepts are applied to computing, i.e how are DFSA's used in programming, though I don't believe it should be too indepth. I'd also like to have a bit more of the class time afforded to converting NFSA's to DFSA's and on context-free Grammar, but I understand that the lack of class time dedicated towards these topics was more likely a result of us just being introduced to them for next year and then expanding on them then.

Context free grammar

Context-free grammar (CFG) describes how sentances in a language are built recursively using a set of rules, the operations given as variables on the left hand side of the equation and the nouns, verbs, etc given as terminals on the right. After doing the exercises in class, I found I had little trouble with the concept. I think I found the concept to be very natural and intuitive after doing DFSA, as the motivations behind the rules seem similar. I decided to look up more about the limitations and extensions around CFGs. An interesting example of an undecidable language, one for which a CFG does not exist, I stumped onto was the case of language that accepts every string. Extending this, it seems that it is in many ways undecidable if two CFGs, that are not precisely equal, describe the same language. I also found it interesting how people had extended the power of CFGs by allowing the nonterminal elements to have arguements, which allows for natural language features such as references and agreement. I'm interested also in seeing how context sensitive grammar works as well as how CFGs are used in computers.

Pumping lemma

The pumping lemma is a tool that we use to determine if a language is regular. In laymen's terms, the idea of the pumping lemma is that an accepted string past a certain length can be broken into parts and that no matter how many times these parts are repeated, the string will still be accepted by the language. More formally, If L is a regular language. Then there is some p that depends on L such that if x is an element of L and |x|>= p, then there exists substrings u,v,w such that x = uvw, where |uv| <= p, v is not empty , and for all k in the Natural numbers, w(uv^k) is an element of L. However, I am unclear on certain aspects of using the pushing theorem. The most trouble I seem to have is with how to break up the string x into uvw and whether we must consider all possible strings u,v,w that could collectively form x. Additionally I can see that a language that does not have the pumping lemma property is not regular, but I am unsure if a language that has the pumping language property is necessarily regular. After searching the internet a bit, it seems that the property apparently holds for some irregular languages, for example, (taken from the wikipedia page on pumping lemma for regular expressions): the language {u(u^R)v : u,v {0,1}+} (strings over the alphabet {0,1} consisting of a nonempty even palindrome followed by another nonempty string) is not regular but can still be "pumped" with p = 4. Suppose w=u(u^R)v has length at least 4. If u has length 1, then |v| ≥ 2 and we can take y to be the first character in v, thus not affecting the palindromic requirement. Otherwise, take y to be the first character of u and note that yk for k ≥ 2 starts with the nonempty palindrome yy, so it's still in the language. I would like to see a bit of attention paid to this example in class, because it seems to be an interesting example of where the pumping theorem may fail.

Converting FSA's to RE

We just finished looking at the mechanism for converting a DFSA to a RE in class. The general idea is to observe the pathways of which each state reaches and exits a particular state and formalize a statement that describes those movements. In doing this we are able to eliminate that particular state and as we repeat the process we eventually remove all the states and are left with a single expression. However, this expression tends to be incredibly complex. Although the expression works and the process is intuitive enough, i'd like to see more examples of simplifying the regular expression that emerges form the process.

DFSA

As we begin to move towards the end of the course, we've largely just finished wrapping up the lectures on deterministic finite state automaton. With the last question one the assignment having us make use of the Cartesian product, some of the important advantage and disadvantage of using DFSA to recognize strings as part of a valid set of languages have become clearer. Particularly, the process is extremely, and quite possibly only, effective when the DFSA is dealing with simple languages. The disadvantage becomes clear when we consider the number of transitions states required as the alphabet increases in size and how the problem space of the method falls prey to combinatorial explosion with small increases in the alphabet size. Infact, it seems as though the complexity of the set of strings accepted languages, perhaps measured by the number of operations involved in the equivalent regular expression, causes the problem space of the DFSA to approach combinatorial explosion as well. Thus, I suspect that the limitation on the complexity of both the language and the alphabet that a DFSA can represent is severely limited or else it requires that the statement be broken up into many smaller machines, the intersection of which is the original regular expression, a process that seems infinitely more tedious then should be necessary. Ultimately I'm curious how DFSA are used in modern computing and how we ensure the stability of their use.

Regular expression

It's extremely fascinating to see the differences between artificial and natural languages. Given the often times unnecessarily cumbersome and ostentatious feel of the rules English, I often find myself appreciating the sublime beauty found in the simplicity of artificial languages. As I begin work on assignment 3, I find it striking how powerful a tool regular expressions can be. I found the concept a bit confusing in lecture, specifically when proving facts about languages, but having worked through a few examples from class i'm beginning to become more confident about the, Having experimented with Regular expressions for searching through text files for the upcoming 207 exercise, i'm beginning to wonder how I ever lived with the incredibly bare bones default find function. If artificial intelligence ever becomes truly self aware, it's comforting to know that their superior powers of communication will help them subjugate our race.