CS341 Discussion Forum

`Discussion section`

Date Stamp :- Thursday, December 19, 2002 at 13:08:21 (CST)
From :-Tazeen
Subject :-Finals
Comments:- You'll be able to pick up your exams soon. As soon as Dr. Rich lets me know when, I'll send out an email to everyone.

Happy Holidays! :-)

Date Stamp :- Tuesday, December 17, 2002 at 17:52:00 (CST)
From :-MB
Subject :-RE:Finals
Comments:- I've just got to this form to ask the same questions. Anybody there, hearing us?

Date Stamp :- Tuesday, December 17, 2002 at 17:20:30 (CST)
From :-Richard Crippen
Subject :-Finals
Comments:- Is there any way that we can actually see our finals? I'd like to see how I did. Is this discussion forum even still active?

Date Stamp :- Friday, December 13, 2002 at 18:43:25 (CST)
From :-Tazeen
Subject :-Re: L = (a)^(2^n)
Comments:- Looks right.

Date Stamp :- Friday, December 13, 2002 at 18:41:54 (CST)
From :-Tazeen
Subject :-Cheatsheet
Comments:- One page cheatsheet is allowed in the exam

Date Stamp :- Friday, December 13, 2002 at 16:56:41 (CST)
From :-questionwriter
Subject :-L = (a)^(2^n)
Comments:- Would the following grammar work for this
S -> T
T -> a
T -> AA
A -> AA
AA -> aa

I supposed u could generate, T->AA, one A->AA to get AAA but you couldn't terminate with that. Any thoughts?

Date Stamp :- Friday, December 13, 2002 at 16:56:10 (CST)
From :-questionwriter
Subject :-L = (a)^(2^n)
Comments:- Would the following grammar work for this S -> T T -> a T -> AA A -> AA AA -> aa I supposed u could generate, T->AA, one A->AA to get AAA but you couldn't terminate with that. Any thoughts?

Date Stamp :- Friday, December 13, 2002 at 10:08:56 (CST)
From :-Shawn Grona
Subject :-Homework grades
Comments:- Never mind my previous question... in case anyone is interested, these are the max scores: 20 130 20 150 20 70 20

Date Stamp :- Friday, December 13, 2002 at 01:33:33 (CST)
From :-?
Subject :-problem pattern
Comments:- Will the exam follow a pattern similar to the exam on Dr.Rich's website?

Date Stamp :- Friday, December 13, 2002 at 01:00:25 (CST)
From :-smartie
Subject :-cheat sheet
Comments:- only if you don't know the material ;-)

Date Stamp :- Thursday, December 12, 2002 at 19:13:31 (CST)
From :-Emanuel Masciarelli
Subject :-Cheat Sheet for Final
Comments:- Can we have one?

Date Stamp :- Thursday, December 12, 2002 at 17:43:26 (CST)
From :-Shawn Grona
Subject :-Homework grades
Comments:- Can someone tell me what the maximum scores on all the homework add up to (homework1_max_score + homework2_max_score + etc...)? I'm not able to tell what the max score on some of my homeworks is supposed to be. Thanks, Shawn Grona

Date Stamp :- Thursday, December 12, 2002 at 14:50:59 (CST)
From :-kurt
Subject :-difference between "x" and "w"
Comments:- I'm having some trouble understanding what is exactly meant by tau("M,x")="M*"; M* on input w. More specifically, where does the w come from? What is w and how is it relevent, especially when you say things like M* on input w: it runs M on x and accepts if M halts on w. I'm not sure of the relationship between w and x. Thanks very much for any help. -kurt

Date Stamp :- Wednesday, December 11, 2002 at 01:23:22 (CST)
From :-Varun
Subject :-Problem posted by Akbar - L16 from Luay's handout
Comments:- L16 = {M|M is a TM and there exists an input whose length < 100 on which M halts}. I fail to understand how this is different from L1. Cant we prove L1 to be not Recursive in the same way as we are L16. Seems like M* could run M on all strings of length <100 only for 99 steps. If after these 99 steps on each string M accepts any string then we accept otherwise we reject. (Isn't this the same reason L1 is R)? Also if someone could tell me how interleaving works exactly. Does it take one step on every string that it can generate and then starts at the first one again; then taking a second step on each of the strings?

Date Stamp :- Tuesday, December 10, 2002 at 19:51:44 (CST)
From :-luay
Subject :-answer to the "person who didn't identify him/herself
Comments:- the reductions for the problems involving the even numbers are correct (make sure you can fully prove the validity of the reduction). For the problem {"M": |L(M)|=2} the language is definitely not in RE, and the proof is by reduction from the complement of HP (let's call it NHP) as follows: tau("M,w")="M*" where M* on input x works as follows: (1) if x is one of the first two (in lexicographical order) strings in Sigma* then accept. (2) otherwise, runs M on w; if M halts on w, M* accepts, otherwise rejects. Notice that if M does not halts on w ("M,w" in NHP) then M* accepts only two strings, i.e., |L(M*)|=2 ("M*" in L). If M halts, then M* accepts all strings, and hence |L(M*)| is not equal to 2, and hence "M*" is not in L! Interesting reduction, ha? keep it in mind!

Date Stamp :- Tuesday, December 10, 2002 at 19:45:12 (CST)
From :-luay
Subject :-answer to Varun
Comments:- What you need to check here is whether M halts on an input of length at most 100. Suppose w is a string and |w|<100. Then you say "run M on w for 99 steps"! What if M halts on w in 100 steps? or in 150 steps? or in 1000000 steps? why did you choose 99? If we say a machine that "accepts w within k steps", then there is no need to look at more than the first k symbols in the input, in which case the number of strings we need to consider is finite, and the number of steps for M to run on w is finite, and hence the language turns out to be recursive. However, when we just limit the length of the string, that does not imply limiting the number of steps on the string. For example, you can easily design a machine that runs forever on the a string of one symbol, or even espsilon...so, limiting the length of the string makes the number of strings finite, but still the machine is not guaranteed to halt on those strings (some or all). this what makes this language not in R. hope this helps.

Date Stamp :- Tuesday, December 10, 2002 at 18:26:25 (CST)
From :-Varun
Subject :-Problem posted by Akbar - L16 from Luay's handout
Comments:- L16 = {M|M is a TM and there exists an input whose length < 100 on which M halts}. I fail to understand how this is different from L1. Cant we prove L1 to be not Recursive in the same way as we are L16. Seems like M* could run M on all strings of length <100 only for 99 steps. If after these 99 steps on each string M accepts any string then we accept otherwise we reject. (Isn't this the same reason L1 is R)? Also if someone could tell me how interleaving works exactly. Does it take one step on every string that it can generate and then starts at the first one again; then taking a second step on each of the strings?

Date Stamp :- Tuesday, December 10, 2002 at 17:23:46 (CST)
From :-
Subject :-"Good Exercise"s from Luay's handout
Comments:- L1 = {|M is a TM and |L(M)|=2} I couldn't figure this one out.------------------- L2 = {|M is a TM and M does not accept all even nos} . This is not RE right? I used to reduction from ~HP to prove this. If M halts on w then M* accepts. --------------------------------- L3 = {|M is a TM and M rejects all even nos.} I got not RE. Same reduction as for L2. ----------------------Do these look right?

Date Stamp :- Tuesday, December 10, 2002 at 14:30:29 (CST)
From :-Tazeen
Subject :-Re: making sure
Comments:- A recursive language is decidable. Anything that is not decidable is undecidable, so not recursive is undecidable. There are two kinds of undecidable languages: RE but not recursive, and not RE.

Date Stamp :- Tuesday, December 10, 2002 at 14:01:59 (CST)
From :-Tazeen
Subject :-Re: Post Correspondence Problem
Comments:- So you have two lists of strings, let the first one be {1, 00, 1} and the second one is {10, 0, 0}. Let the elements of the first list be x1, x2, x3 and the elements of the second list be y1, y2, y3. Then the concatenation of x1 x2 = y1 y2 = 100, so these are in the language.
Now consider another pair of lists, let the first one be {10, 110} and the second one be {101, 101}.
You're checking to see if any same combination of elements for the two lists results in the same string.
Take 101 from the second list, the only thing that works from the first list is 10, but the strings are not the same so you must concatenate something else.
so far you have x1 = 10 and y1 = 101
now y1 y2 = 101101 and x1 x2 = 10110
try again y1 y2 y2 = 101101101 and x1 x2 x2 =10110110
There's always a string that you can concat that seems to take you closer to having the same strings but one of them is always one symbol longer than the other one.
These pairs would not be in the language but there never comes a time when you can say no so the problem is not recursive.

Date Stamp :- Monday, December 09, 2002 at 23:00:18 (CST)
From :-luay
Subject :-
Comments:- this language you are talking about, Akbar, is not recursive, and running the machine in an interleaved mode won't help (btw, remember that if the language is recursive, there is really no need for dovetailing; this technique is just used for RE languages). Remember that in order for a language to be recursive, there must exist at least one TM that ALWAYS halts (accepts strings in the language, and rejects other strings). In the solution you gave, if M accepts a string, then M will halt and accept; however, what happens when there are no such strings accepted by M? How can M halt and reject? It's going to take forever, even with interleaved mode run, to go over the strings (since the machine might run forever on some of the strings). Recall that I said in the review session that limiting the length of the string in general does not help making the language recursive!!! So, to summarize, the problem in your approach is that the machine that you "claimed" would decide the language would never halt and reject when it should! luay

Date Stamp :- Monday, December 09, 2002 at 22:58:58 (CST)
From :-luay
Subject :-
Comments:- this language you are talking about, Akbar, is not recursive, and running the machine in an interleaved mode won't help (btw, remember that if the language is recursive, there is really no need for dovetailing; this technique is just used for RE languages). Remember that in order for a language to be recursive, there must exist at least one TM that ALWAYS halts (accepts strings in the language, and rejects other languages). In the solution you gave, if M accepts a string, then M will halt and accept; however, what happens when there are no such strings accepted by M? How can M halt and reject? It's going to take forever, even with interleaved mode run, to go over the strings (since the machine might run forever on some of the strings). Recall that I said in the review session that limiting the length of the string in general does not help making the language recursive!!! So, to summarize, the problem in your approach is that the machine that you "claimed" would decide the language would never halt and reject when it should! luay

Date Stamp :- Monday, December 09, 2002 at 22:02:46 (CST)
From :-Akbar Noorani
Subject :-problem 7d.
Comments:- d) L = {“M” : there exists a string w, |w| < 100, such that M accepts w} I really felt that this one would be recursive, because thre is only a finite number of strings to be tested. The only probably i see with this is if the machine M gets stuck on an input w. But, if we run this in an interleaved mode (from Luay's descussion) it should take care of this problem, and if such a w exists it should find it or else return false. can someone who understand my point, please reply. i would totally apreciate it.

Date Stamp :- Monday, December 09, 2002 at 19:18:18 (CST)
From :-
Subject :-making sure
Comments:- Is solvable the same as decidable? A language that is undecidable is one that has a grammar which is not RE or is not R enough?

Date Stamp :- Monday, December 09, 2002 at 19:13:26 (CST)
From :-
Subject :-Post Correspondence Problem
Comments:- Why is the post correspondence problem not recursive? Aren't we checking over a list of finite number of strings? So we could halt and say no when theres no similar strings at the same position in both the lists.

Date Stamp :- Monday, December 09, 2002 at 19:05:51 (CST)
From :-
Subject :-
Comments:- ignore the previos message

Date Stamp :- Monday, December 09, 2002 at 19:04:41 (CST)
From :-
Subject :-Final
Comments:- Can someone tell me the chapters covered after the first and second midterm. Tazeen could you also give a rough idea of the weightage that will be given to the 3 portions of the notes (i.e. stuff from the first midterm, second midterm and after).

Date Stamp :- Monday, December 09, 2002 at 17:02:00 (CST)
From :-Tazeen
Subject :-Re: Length of TM
Comments:- That's point 3 in the solution, if it goes right forever on the tape on input w at some point the head's going to go past the last symbol in the input so it will be on a blank,(it is assumed that the tape contains only blanks other than the input w).
At some point it will be in some state p, (a TM has a finite number of states and it keeps going right, so it doesn't halt so it must be in at least one state more than once), after a finite number of steps it will again be in state p and if it hasn't moved left yet, then it's going to do the same steps as it did when it was first in state p and read a blank on the tape, so it will never move left. So you can say no.

Date Stamp :- Monday, December 09, 2002 at 15:16:34 (CST)
From :-Tazeen
Subject :-Re: 2N or 2^N
Comments:- For people who attended the last discussion session, it's 2N :-)

Date Stamp :- Monday, December 09, 2002 at 14:07:54 (CST)
From :-Luay
Subject :-Solutions (important)
Comments:- Please notice that what I provided were mostly solution sketches rather than full solutions. Make sure you know how to write the full formal proofs. luay

Date Stamp :- Monday, December 09, 2002 at 13:07:04 (CST)
From :-Luay
Subject :-Review Problems and Solutions
Comments:- I have posted the solutions (the handout includes the problems themselves too) at: http://www.cs.utexas.edu/users/nakhleh/final_review_fall02_sol.ps (for PS format) http://www.cs.utexas.edu/users/nakhleh/final_review_fall02_sol.pdf (for PDF format) The solutions also contain a couple of more suggested exercises that will help you better understand reductions. Good luck on your finals. luay

Date Stamp :- Monday, December 09, 2002 at 11:15:01 (CST)
From :-Katie
Subject :-Luay's Problems
Comments:- I wasn't able to attend the review session last night. Does anyone know where I can get a copy of Luay's Review Problems? (hard or electronic, doesn't matter) Thanks! Katie

Date Stamp :- Monday, December 09, 2002 at 07:10:04 (CST)
From :-
Subject :-Solutions for Luay's Review Problems
Comments:- Could anyone please post the address for the solutions? I think I wrote the address wrong, and I haven't been able to find it. Thanks.

Date Stamp :- Monday, December 09, 2002 at 02:44:09 (CST)
From :-Chiu
Subject :-Length of TM
Comments:- This is regarding prac problem 21 q1b. The solution says to assume that a TM M is deterministic. Why do we have to assume this? On on a given tape cant M just go forever to the right? Isnt this just a way for it to never halt?

Date Stamp :- Sunday, December 08, 2002 at 16:29:35 (CST)
From :-Jason
Subject :-Homework 7 prob 3
Comments:- Where is the Post Coresponendce problem in our lecture notes?

Date Stamp :- Saturday, December 07, 2002 at 21:44:24 (CST)
From :-Justin
Subject :-2N or 2^N?
Comments:- I was wondering if we decided the answer to this question from last wed. discusion.

Date Stamp :- Friday, December 06, 2002 at 18:12:55 (CST)
From :-Tazeen
Subject :-Final exam
Comments:- I've posted the times of the final on the main page. Attend either one.
One of the big questions on the exam most likely will be asking whether a particular language is regular, CF but not regular, recursive but not CF, RE but not recursive, or not RE. So you need to know how to prove those.
It's possible you'll be asked to write an unrestricted grammar for a language.
You'll probably have to draw out Turing Machines.
Dr. Rich makes the exam so I really don't know how she's going to divide it up.

Date Stamp :- Friday, December 06, 2002 at 17:51:58 (CST)
From :-
Subject :-Final
Comments:- Can someone tell me the chapters covered after the first and second midterm. Tazeen could you also give a rough idea of the weightage that will be given to the 3 portions of the notes (i.e. stuff from the first midterm, second midterm and after).

Date Stamp :- Thursday, December 05, 2002 at 01:38:20 (CST)
From :-
Subject :-Final Exam Sched
Comments:- There is only 1 final exam time we can take right?

Date Stamp :- Tuesday, November 26, 2002 at 11:33:36 (CST)
From :-Tazeen
Subject :-Re: Final Exam Review
Comments:- It's on December 8th by Luay 6 - 10 pm Tay 2.106

Date Stamp :- Tuesday, November 26, 2002 at 10:42:34 (CST)
From :-Shawn Grona
Subject :-Final Exam Review
Comments:- Tazeen- When is the review for the final exam scheduled? And just out of curiousity who will be hosting it? I want to make sure I'm available. Thanks, Shawn Grona

Date Stamp :- Friday, November 22, 2002 at 18:09:30 (CST)
From :-Tazeen
Subject :-Re: HW 6 #4c
Comments:- Hi Brian, sorry for replying after the homework is due .. but I'm assuming you're still interested to know this for the exam. If f(x) is defined for a certain x, then the machines will halt, if f(x) is not defined for a certain x, the machines will not halt which is what you want according to the problem definition. It's how machines behave for RE languages, the only requirement is that they must halt on strings that are accepted in the language, they are not required to say no to strings that are not in the language.
Was that what you were asking?
If a machine can lexicographically enumerate strings that are in a language then the language is recursive. That's because if you have such an enumerator for the language, you can say yes to a certain string if the enumerator writes it out, and you can say no to a string as soon as the enumerator writes out something that should come later in the order than the string you're interested in. Not sure if that's exactly what you were asking about but hope it helps :-)

Date Stamp :- Thursday, November 21, 2002 at 12:42:38 (CST)
From :-Brian
Subject :-HW 6 #4c
Comments:- Tazeen, The only problem I am having with the homework is problem 4c. I understand that non-determinism can be used to help solve semi-decidable problems, but even if it's added to get part a&b working, doesn't the resulting machine still not halt because there are no correct solutions? I vaguely remember Dr. Rich talking about impozing an ordering in class to help, but I can't seem to find a mention of it in the notes. Any clue would be appreciated. Thanx!

Date Stamp :- Thursday, November 21, 2002 at 10:59:07 (CST)
From :-Tazeen
Subject :-Re: Enumeration Problem 2
Comments:- P is used to indicate that you've finished enumerating an element. It makes no changes to the tape.
So in the example, it's going to write 1 on the tape, then write another 1, there has to be a way to know that it hasn't finished after writing the first 1, only after writing the second 1, that's what P is used for.

Date Stamp :- Wednesday, November 20, 2002 at 21:30:37 (CST)
From :-James
Subject :-Enumeration Problem 2
Comments:- I'm not exactly sure what the macro P does. Can someoen give an example? With the input tape and output tape?

Date Stamp :- Wednesday, November 20, 2002 at 21:06:05 (CST)
From :-James
Subject :-RE:Macro Lang
Comments:- I think she means the shorthand way of doing things. Like R1 would be go right till you find a 1. it's in lecture 20

Date Stamp :- Wednesday, November 20, 2002 at 20:47:38 (CST)
From :-
Subject :-macro language
Comments:- just wanted to make sure what the macro language she was referring to in Q1 was. thanks in advance

Date Stamp :- Wednesday, November 20, 2002 at 20:02:09 (CST)
From :-James
Subject :-Some Machines
Comments:- In the hw, Rich has said to use some of the machines defined in class. R(-) goes right to the end of the input right? Are there any other machines she defined?

Date Stamp :- Wednesday, November 20, 2002 at 17:06:50 (CST)
From :-
Subject :-unary encoding
Comments:- Sam, your doubts are perfectly valid. In theory, there is no such thing as "unary numbers". I guess this is to be expected from people that tell you 1 is prime and don't know how to use set notation...

Date Stamp :- Wednesday, November 20, 2002 at 16:48:47 (CST)
From :-Shawn Grona
Subject :-Tutor Recomendation
Comments:- Does anyone have the name of a tutor in 341/Automata Theory? Thanks for any input, Shawn Grona static@cs.utexas.edu

Date Stamp :- Wednesday, November 20, 2002 at 07:14:43 (CST)
From :-sam
Subject :-unary encoding
Comments:- Shawn, I think that unary encoding means represent numbers with only 1 symbol. For instance, 1 = 1, 2 = 11, 3 = 111. So if the input string was abaa, the machine needs to output 111. I'm not sure what you output in the case of epsilon.

Date Stamp :- Tuesday, November 19, 2002 at 22:09:23 (CST)
From :-Shawn Grona
Subject :-Problem 3
Comments:- I don't understand what is meant by the unary encoding of max(#a(x),#b(x)). Can someone help? Thanks, Shawn

Date Stamp :- Tuesday, November 19, 2002 at 11:48:09 (CST)
From :-Tazeen
Subject :-Re: Project 2: Section 1, Problem 9
Comments:- Are you using quotes around invert and square in lex? Don't need to use those.

Date Stamp :- Tuesday, November 19, 2002 at 11:46:00 (CST)
From :-Tazeen
Subject :-Re: part 1, ques 3
Comments:- Yes, turn in the entire y.output

Date Stamp :- Tuesday, November 19, 2002 at 00:53:24 (CST)
From :-
Subject :-errors
Comments:- It should loop and prompt for input.

Date Stamp :- Tuesday, November 19, 2002 at 00:43:51 (CST)
From :-arjun
Subject :-looping
Comments:- on an error, is it supposed to loop and ask for input again? mine just quits right after i get an error, even though i tried dr. rich's solution. i'm not sure if this is related, but when i run the program normally and it receives a correct input, it outputs the result and quits.

Date Stamp :- Monday, November 18, 2002 at 22:28:39 (CST)
From :-
Subject :-Project 2: Section 1, Problem 9
Comments:- I'm having a lot of trouble trying to add invert() and square() into the grammar. Anyone have any suggestions as to how I should add it in the lex file? I think I understand how it should be implemented in the yacc file. But with lex, I'm not sure what I need to do because in my attempts, when I've run the program, "invert" and "square" return syntax errors.

Date Stamp :- Monday, November 18, 2002 at 21:43:59 (CST)
From :-
Subject :-Trace
Comments:- How do we use the debug to trace by hand? I read the yacc help file but didn't see that option...

Date Stamp :- Monday, November 18, 2002 at 20:11:51 (CST)
From :-
Subject :-part 1, question 3
Comments:- Am I correct in understanding that we are to include the _entire_ yacc output file in our documentation?

Date Stamp :- Monday, November 18, 2002 at 18:47:23 (CST)
From :-
Subject :-Re:Part 1 Section 2
Comments:- You just have extend the grammar to accept '*' and '/'.

Date Stamp :- Monday, November 18, 2002 at 17:11:21 (CST)
From :-
Subject :-Part 1 Section 2
Comments:- Hi, Just wondering about the numbers we get for part 2 after we add the '/' and '*'. We should be getting numbers consistent with the parsing format of part 1 right. In short do we only extend the grammar to accept '*' and '/' or do we need to make sure that we get right answers that follow normal convention like 9/3-3 would be 0.

Date Stamp :- Monday, November 18, 2002 at 16:47:38 (CST)
From :-Richard Crippen
Subject :-re: invert and square
Comments:- I hope I'm not giving too much away here, but I'll try to keep it pretty basic. To perform square(#) and invert(#) in C-code, try to think what these functions look like using only the symbols we already have (+,-,*,/) I hope this helps and isn't too specific.

Date Stamp :- Sunday, November 17, 2002 at 22:45:45 (CST)
From :-Tazeen
Subject :-Project Discussion
Comments:- Hi people,
It's great to see everyone's participation in the discussion forum, however remember that the project is not meant to be a joint effort. You're encouraged to help each other as far as knowing the difference between dos and unix files and printing things, but please refrain from discussing the exact details of how you're implementing functions etc. I've deleted posts from chiu and kurt, you're sharing too much :)

Date Stamp :- Friday, November 15, 2002 at 14:37:21 (CST)
From :-Matt
Subject :-invert and square definitions
Comments:- I am wondering if anyone can give me a hint as to how to add invert and square properly to the lex file. I don't understand what action to take so that it will correspond properly to the yacc rule expr | 'invert' '(' expr ')' {$$=0-$3;}. Please help me understnad this thing. Thanks.

Date Stamp :- Friday, November 15, 2002 at 00:02:30 (CST)
From :-kak
Subject :-error recovery
Comments:- so it's okay to use Rich's error recovery solution?

Date Stamp :- Thursday, November 14, 2002 at 23:26:43 (CST)
From :-
Subject :-Found it
Comments:- Just recompile the a.out

Date Stamp :- Thursday, November 14, 2002 at 23:24:28 (CST)
From :-Seth
Subject :-Syntax Error
Comments:- I am getting a syntax error when I modify my yacc file. I know the syntax I am putting in is correct, but when I try to do a mult. problem I get a syntax error. Is anyone else having this problem? My addition and subtraction still work and the file compiles it just won't multiply. I have added the * to my lex file. Suggestions? Thanks, Seth

Date Stamp :- Thursday, November 14, 2002 at 22:38:42 (CST)
From :-
Subject :-bad math okay?
Comments:- just to make sure, it's okay if the program returns the wrong numbers for the first few questions, right? kak

Date Stamp :- Wednesday, November 13, 2002 at 19:59:56 (CST)
From :-ak
Subject :-interperting .txt files
Comments:- "If you have trouble doing this, retype the files..." - cute! Running dos2unix on the files seems to help. There is probably some obscure learning value in being provided with unusable sources...

Date Stamp :- Monday, November 11, 2002 at 18:36:07 (CST)
From :-kurt
Subject :-Re: lex compiling trouble
Comments:- Okay, now I really figured it out. You need a newline (blank line) as the last char. at the end of the lex file. I din't have a newline as the last line, so it couldn't recognize the end of file.

Date Stamp :- Monday, November 11, 2002 at 17:58:48 (CST)
From :-kurt
Subject :-Re: lex compiling trouble
Comments:- okay, what seems to compile is when i append the following text after the original stuff: %% main () {} Is this really necessary and will change the output to function any differently? thanks, -k

Date Stamp :- Monday, November 11, 2002 at 17:44:38 (CST)
From :-kurt
Subject :-lex compiling trouble
Comments:- everytime i try to run lex on simple test files (including Rich's initial file) i get errors. even if i retype the file, i always get "line 4: EOF encountered inside an action". Does anyone know what's going on here? The only lex file that doesn't generate errors is the file containing "%%" and that's it. I'm running lex (which i believe is linked to flex) on the linux computers here in the cs labs. thanks for any help, kurt

Date Stamp :- Monday, November 11, 2002 at 13:52:02 (CST)
From :-Tazeen
Subject :-hand trace
Comments:- If you're confused about how to do the handtrace, read section 4: how the parser works on this page http://www.cs.utexas.edu/users/ear/cs341/yaccpaper.htm

Date Stamp :- Sunday, November 10, 2002 at 16:29:56 (CST)
From :-Tazeen
Subject :-Re: Project 2 hand trace
Comments:- If the results of the hand trace and the automatic trace are somewhat different, don't worry about it. The main thing there is that you have a general idea of how it works and make sure you identify the conflicts correctly.

Date Stamp :- Sunday, November 10, 2002 at 14:55:55 (CST)
From :-Jennifer
Subject :-Project 2: tracing input by hand
Comments:- I'm really lost in step 4, especially 4A. My work on A appears to differ from part B. Are they suppose to differ--i.e., will B leave out following some states? I just might be confused as how I should be following in some states for A, as I assumed that if a state did not have a goto then I'd return to the previous state. Am I doing this right?

Date Stamp :- Friday, November 08, 2002 at 19:37:52 (CST)
From :-sam
Subject :-shift/reduce
Comments:- You should be getting those messages. They are letting you know that the grammar contains shift/reduce ambiguities. These were discussed in class during the lectures on lex/yacc.

Date Stamp :- Friday, November 08, 2002 at 15:34:41 (CST)
From :-
Subject :-Project
Comments:- Hi Did anyone get warning/error messages when doing the 1st question of the project? I have retyped the files. yacc expr.y gives a message "conflicts : 4 shift/reduce" cc y.tab.c gives some warning message. Any one knows what it means or if it even matters? Thanks

Date Stamp :- Tuesday, November 05, 2002 at 13:38:34 (CST)
From :-Tazeen
Subject :-Review
Comments:- The answers to the review are posted on the newsgroup, utexas.class.cs341
After you log in to a unix machine, type xstart. This will give you windows environment.
Right click, this will show a menu box.
Click on applications. Click on Netscape. Go to the link Luay posted. Save the ps or pdf file.
Right click. Click on Applications. Click on Acrobat, give it the path to your pdf file. or Click on Ghostview and give it the path to your ps file.

Date Stamp :- Tuesday, November 05, 2002 at 11:19:12 (CST)
From :-Richard Crippen
Subject :-Luay's Review
Comments:- Here's my Unix deficiency showing again. How do we view ps or pdf files on the Unix machines in the lab?

Date Stamp :- Tuesday, November 05, 2002 at 11:11:54 (CST)
From :-Richard Crippen
Subject :-re:pumping lemma question
Comments:- I'd like to answer your last question, Kurt, even though you see the answer. I'm answering just to make sure I see it correctly, so anyone feel free to correct me. Assume L={wwR:w is an element of {a,b}*} is CF. Kurt chose w=a^Mb^Mb^Ma^M as his string to pump. If vxy is in the b region, pumping in will result in an even number of b's being added. Kurt, you are correct that this no longer satisfies the a^Mb^Mb^Ma^M, but the resulting string is still in L, namely wwR. Therefore, the string can be pumped, and pumping on this string fails to say that L is not CF. Does that sound right to everyone else?

Date Stamp :- Tuesday, November 05, 2002 at 03:52:26 (CST)
From :-kurt
Subject :-re: pumping lemma question
Comments:- okay, yes, i see, i was just looking at it the wrong way. thanks.

Date Stamp :- Tuesday, November 05, 2002 at 03:30:24 (CST)
From :-kurt
Subject :--re: pumping lemma question
Comments:- Arjun - okay, if v's and y's are b's only and you pump, then wouldn't that make a string not in the language, because the number of b's = number of a's in my w. Then there'd be more or less b's than a's. thanks for the time, kurt

Date Stamp :- Tuesday, November 05, 2002 at 03:29:10 (CST)
From :-kurt
Subject :-pumping lemma problem
Comments:- I have a question about the Pumping Lemma on Context Free languages. The language L {ww^R : w is an element of {a,b}*} is CF right? Then what if I try to prove that it's not CF and I take the w = a^M b^M b^M a^M, then can't we show that there's no case where the rule |vxy| <= M? I can't see how using this w, we can find a decomposition where it fits the rules of the PL. What am I not understanding here? Thanks in advance for your time.

Date Stamp :- Tuesday, November 05, 2002 at 00:44:56 (CST)
From :-arjun
Subject :-re: pumping lemma question
Comments:- you have to examine all cases of partitioning w=uvxyz and show that for each case, pumping in or out will give you a string not in the language. if for any case you cannot show this, then you cannot assert that L is not CF. In your case, when v and y are both in the b-region (remember, you can't pick (v,y)), then if you pump in or out, you will take out or put in an even number of bs and the string will still be in the language. hope this helps, arjun

Date Stamp :- Tuesday, November 05, 2002 at 00:21:10 (CST)
From :-kurt
Subject :-pumping lemma problem
Comments:- I have a question about the Pumping Lemma on Context Free languages. The language L {ww^R : w is an element of {a,b}*} is CF right? Then what if I try to prove that it's not CF and I take the w = a^M b^M b^M a^M, then can't we show that there's no case where the rule |vxy| <= M? I can't see how using this w, we can find a decomposition where it fits the rules of the PL. What am I not understanding here? Thanks in advance for your time.

Date Stamp :- Monday, November 04, 2002 at 22:20:46 (CST)
From :-Ham
Subject :-Where are the answers to the Review?
Comments:- I read they were supposed to be on the mailing list. I've recieved emails from Tazeen so i assume i'm on the list. So where is it?

Date Stamp :- Monday, November 04, 2002 at 22:07:56 (CST)
From :-Tazeen
Subject :-Re: pumping lemma
Comments:- If i=2, uv^ixy^iz = uv^2xy^2z = uvvxyyz ..
For example if L = a^N b^N c^N, let w=a^M b^M c^M
case 1: v is in a's, y is in b's
v = a^r
y = b^s
uv^ixy^iz = a^(M +(i-1)r) b^(M+(i-1)s) c^M

Detailed Explanation:
Choose the rest of the variables such that when you put them in order you get back w.
u = a^p
x = a^(M-(p+r))b^t
z=b^(M-(s+t))c^M

Pumping up, i=2
uv^2xy^2z = a^p a^r a^r a^(M-(p+r)) b^t b^s b^s b^(M-(s+t)) c^M
uv^2xy^2z = a^p a^(2r) a^(M-(p+r)) b^t b^(2s) b^(M-(s+t)) c^M
uv^2xy^2z = a^(M+r) b^(M+s) c^M
From the condition |vy|>0, either r, s or both are greater than 0. In all three cases, uv^2xy^2z is not in L.
Need to take care of all other cases to show L is not a CFL.

Date Stamp :- Monday, November 04, 2002 at 21:47:19 (CST)
From :-luay
Subject :-answers to Problem 1 on the review handout
Comments:- I have just posted the answers to Problem 1 on the review handout to the mailing list utexas.class.cs341 You can compare your answers against mine. Remember: I only provided the answers; you still need to know how to prove your answer.

Date Stamp :- Monday, November 04, 2002 at 21:46:18 (CST)
From :-Tazeen
Subject :-Re: practice exam
Comments:- A lexicographic enumeration is an enumeration in the same order as things are listed in the dictionary.. so a is before aa is before aab and so on

Date Stamp :- Monday, November 04, 2002 at 20:37:22 (CST)
From :-meghana
Subject :-pumping lemma
Comments:- when you use the pumping lemma for CFLs, if you say uv^ixy^iz and i=2 do you add i times the character or multiply?

Date Stamp :- Monday, November 04, 2002 at 18:40:01 (CST)
From :-
Subject :-
Comments:-

Date Stamp :- Monday, November 04, 2002 at 18:05:48 (CST)
From :-Matt
Subject :-practice exam
Comments:- What's a lexicographic enumeration?

Date Stamp :- Monday, November 04, 2002 at 11:05:35 (CST)
From :-luay
Subject :-PDA to CFG
Comments:- Dr Rich told me that she requires students to know only the conversion from CFG to a PDA but not the other way around. Nevertheless, I have put the algorithm for PDA->CFG for those students who asked about it, and for those who might be curious.

Date Stamp :- Monday, November 04, 2002 at 09:27:04 (CST)
From :-sam
Subject :-PDA -> CFG
Comments:- I have written in my notes that we will not have to go from a PDA to a CFG. Anyone else remember Prof. Rich saying this?

Date Stamp :- Monday, November 04, 2002 at 08:35:25 (CST)
From :-Luay Nakhleh
Subject :-PDA to CFG
Comments:- Some students have asked about an algorithm that converts a PDA into a CFG. You can find it at: http://www.cs.utexas.edu/users/nakhleh/PDA2CFG.ps Luay

Date Stamp :- Sunday, November 03, 2002 at 22:51:41 (CST)
From :-Luay Nakhleh (nakhleh@cs)
Subject :-2nd midterm review session
Comments:- I have posted the list of the review problems under my homepage: http://www.cs.utexas.edu/users/nakhleh/2nd_midterm_review.ps (PS) http://www.cs.utexas.edu/users/nakhleh/2nd_midterm_review.pdf (PDF) hope the review session was helpful. Good luck. Luay

Date Stamp :- Saturday, November 02, 2002 at 09:53:26 (CST)
From :-sam
Subject :-->*
Comments:- Roy, I believe that means remove all single nonterminals, B, that are derivable by a single nonterminal, A. The * applies to -> not the B.

Date Stamp :- Friday, November 01, 2002 at 19:21:56 (CST)
From :-roy depuis
Subject :-conversion to Chomsky NF
Comments:- In the Lecture Notes 16 Conversion to Chomsky Normal Form 3.2 it says "For all non-terminals A, find all nonterminals B such that A --> *B, A != B." What does the '*' mean? Does it mean anything can come before B?

Date Stamp :- Friday, November 01, 2002 at 12:34:16 (CST)
From :-
Subject :-Baker's class on Thurs
Comments:- Dr Baker talked about decision procedures for c.f.l. on Thursday. Does anybody know where in the notes it is found? Cant seem to find it anywhere. Thanks

Date Stamp :- Wednesday, October 30, 2002 at 11:54:11 (CST)
From :-Tazeen
Subject :-Re: Output on project 2
Comments:- If you want everything to be saved to a file called filename, try this: script filename
Everything that you type or that's printed on the screen will be saved to filename until you type exit
There will be some junk in the file that you can clean up if you want.
if you're working in Taylor basement, print the file by typinglpr -Plw36 filename lw36 is the name of the printer. To see how many jobs are already on that printer type lpq -Plw36. You can also check your job number from that. To remove your job from the printer queue, type lprm -Plw36 jobnumber

Date Stamp :- Tuesday, October 29, 2002 at 18:53:58 (CST)
From :-Richard Crippen
Subject :-re: output on project 2
Comments:- For anyone reading this who was wondering the same thing as I was, I found out the solution. When you run the program, type a.out >> filename.out, where filename.out is some file. This pipes the output to the specified file name. If the files doesn't exist, it creates it, and if it does exist, it appends the data onto the end of the file.

Date Stamp :- Monday, October 28, 2002 at 19:32:31 (CST)
From :-other 341 section
Subject :-CFG question
Comments:- If there is a language of {a,b}* such that the number of a's = 3 times the number of b's. How would you go about creating a CFG for it? There is no particular ordering of a's or b's. thanks.

Date Stamp :- Monday, October 28, 2002 at 16:12:01 (CST)
From :-Richard Crippen
Subject :-output on project2
Comments:- Ok, I'll admit it, I'm a Unix novice. How do we pipe the output to print? And please keep the instructions simple, I've only dabbled in Unix.

Date Stamp :- Thursday, October 17, 2002 at 14:55:25 (CDT)
From :-andrea
Subject :-Help with 1d
Comments:- Does anyone have any ideas on 1d? Thanks.

Date Stamp :- Thursday, October 17, 2002 at 14:47:11 (CDT)
From :-Tazeen
Subject :-Re: 1a - S --> aS | epsilon same as S --> a | aS?
Comments:- Try to generate the string ba

Date Stamp :- Thursday, October 17, 2002 at 14:36:12 (CDT)
From :-Gunter
Subject :-1a - S --> aS | epsilon same as S --> a | aS?
Comments:- Is S --> aS | epsilon the same thing as as S --> a | aS? Does the same follow for Sb? Can't we generate any string with this?

Date Stamp :- Thursday, October 17, 2002 at 11:46:18 (CDT)
From :-Tazeen
Subject :-Re: tips on problems
Comments:- do you mean 3e? try to think of it as x#uxv :x, u, v are elements of {0, 1}*
Try to work from the outside in
For the last PDA, draw one for ww^R.. have the first state put a bottom of the stack symbol on the stack on the transition to the second state.. from the second to last state, you'll pop off the bottom of the stack symbol and go to the final state.. now to make it L1*, have a transition going from the second to last state to the second state, the transition will pop the bottom of the stack symbol and then push it back on.. it pops it off to check that it's reached the bottom of the stack.. and then it pushes it back on to start L1 again.
Hope that helps :)

Date Stamp :- Thursday, October 17, 2002 at 01:54:00 (CDT)
From :-arjun
Subject :-tips on problems
Comments:- does anyone have any tips on 2e or 5c (the last pda) i've been workin on them for hours and gotten nowhere

Date Stamp :- Wednesday, October 16, 2002 at 19:52:23 (CDT)
From :-Tazeen
Subject :-Discussion session 10/16
Comments:- In the discussion session, we were talking about 2c and calling it 2a. They are different. In 2a the order matters.
For 3d) we discussed three cases but missed the last one.
(i) 0#1
(ii) u0#1u^R : u = 1{1,0}*
(iii) u 0 1^k # 0^k 1 u^R
(iv) 1^k # 0^k 1

Date Stamp :- Friday, October 11, 2002 at 20:43:14 (CDT)
From :-ak
Subject :-inconsistencies
Comments:- I'd like to point out that, being a mathematician, "f is nice iff whenever L2 is regular L1 is regular" to me means "f is nice iff f(L) is regular implies L is also regular", and _not_ "L implies f(L)". There is no "other direction" in this definition. To be consistent with the correct answer the definition should have been "f is nice iff (L is regular iff f(L) is regular" (i.e., a nice function preserves regularity and non-regularity, if there is such a term). And, by the way, 1 is not prime. :)

Date Stamp :- Wednesday, October 09, 2002 at 10:45:46 (CDT)
From :-kurt
Subject :-grades when?
Comments:- just curious when we should expect to see our project and test grades. thanks. kurt

Date Stamp :- Tuesday, October 08, 2002 at 11:56:49 (CDT)
From :-Tazeen
Subject :-L*=a*
Comments:- You're right the answer's assuming prime numbers include 1.

Date Stamp :- Tuesday, October 08, 2002 at 01:10:54 (CDT)
From :-L*=a*
Subject :-arjun
Comments:- this is how i figured it: L = {set of a^+ where the length is prime} so this is L = {aa,aaa,aaaaa,aaaaaaa, ... } (i don't count 1 as prime but i think the answer does..) so L = {aa,aaa,aaaaa,aaaaaaa, ... } * so just like {a,b}* = {epsilon,a,aa,aaa,ab,abba,bababa...} L* = {epsilon, aa,aaa,aaaa,aaaaa..} so I thought it should be L* = epsilon U (aa(a*)) but if 1 is prime then L*= a* hope this helps (i think i might've posted twice ...typo in the other one)

Date Stamp :- Tuesday, October 08, 2002 at 01:09:35 (CDT)
From :-arjun
Subject :-L*=k*
Comments:- this is how i figured it: L = {set of a^+ where the length is prime} so this is L = {aa,aaa,aaaaa,aaaaaaa, ... } (i don't count 1 as prime but i think the answer does..) so L* = {aa,aaa,aaaaa,aaaaaaa, ... } * so just like {a,b}* = {epsilon,a,aa,aaa,ab,abba,bababa...} L* = {epsilon, aa,aaa,aaaa,aaaaa..} so I thought it should be L* = epsilon U (aa(a*)) but if 1 is prime then L*= a* hope this helps

Date Stamp :- Monday, October 07, 2002 at 23:47:12 (CDT)
From :-kurt
Subject :-don't understand this problem
Comments:- There is still a problem I don't get. Given L={w elem. of a^+ : |w| is prime}, is L* regular? answer = L* = a*. how is this? thank you, kurt

Date Stamp :- Monday, October 07, 2002 at 18:51:47 (CDT)
From :-Tazeen
Subject :-homework 3 posts
Comments:- Hey,
Saw the posts about homework 3 too late today, the answers are posted so you can check them out.

Date Stamp :- Monday, October 07, 2002 at 18:49:35 (CDT)
From :-Tazeen
Subject :-Minimal machine
Comments:- Actually I confirmed it with her that it's supposed to work only for DFSM. So if you have a NDFSM, need to convert it to a DFSM first, then use the algorithm.
It's the exact same algorithm she's using in lecture notes 10 page 9, I just write it a little differently.

Date Stamp :- Monday, October 07, 2002 at 16:31:59 (CDT)
From :-Sam
Subject :-tazeen's algorithm for finding a minimal machine
Comments:- Tazeen, did you ever find out if your algorithm works for a NDFSM? Your approach seems to be quite a bit easier than the one prof. Rich gave.

Date Stamp :- Monday, October 07, 2002 at 15:26:32 (CDT)
From :-Joe
Subject :-Re: 2d
Comments:- For #2d, you would need to pump somehow to get equal number of 0's and 1's.

Date Stamp :- Monday, October 07, 2002 at 13:55:49 (CDT)
From :-Shawn Grona
Subject :-2d
Comments:- Thats, 2d on the comment below... On 2d I don't know how to start the pumping lemma.

Date Stamp :- Monday, October 07, 2002 at 13:54:57 (CDT)
From :-Shawn Grona
Subject :-2d
Comments:- Thanks for the help on 2e, thats what I thought it was. On 2e, I don't even know how to start the pumping lemma... Tazeen? Thanks, Shawn Grona

Date Stamp :- Monday, October 07, 2002 at 13:46:16 (CDT)
From :-Joe
Subject :- #2 (a)
Comments:- Does the 'R' in #2(a) denote a power of y, or does it mean the reverse of y?

Date Stamp :- Monday, October 07, 2002 at 12:28:59 (CDT)
From :-Tazeen
Subject :-HW3 2e
Comments:- # is an input alphabet so you can transition on it. |x|.|y| =5 0 means that the length of the symbols before you get a # times the length of the symbols after you get a # should be a multiple of 5.
This is only possible if either |x| is a multiple of five or |y| is a multiple of 5.
It is possible to draw a FSM for it.

Date Stamp :- Monday, October 07, 2002 at 11:14:41 (CDT)
From :-Sam
Subject :-# symbol
Comments:- I think you must include it for that language

Date Stamp :- Monday, October 07, 2002 at 10:42:17 (CDT)
From :-Shawn Grona
Subject :-2(e)
Comments:- In drawing a FSM for this problem, can we use the # symbol as a transition? Thanks

Date Stamp :- Monday, October 07, 2002 at 08:37:54 (CDT)
From :-2(e)
Subject :-Sam
Comments:- Was wondering if anyone could give me any hints on this one? I assume it's similar to the other mod problem that was regular, but I can't see it... tia

Date Stamp :- Saturday, October 05, 2002 at 17:13:32 (CDT)
From :-Tazeen
Subject :-L(M)^R
Comments:- If L(M) is {a, ab, abb} then L(M)^R is {a, ba, bba}.

Date Stamp :- Saturday, October 05, 2002 at 13:49:43 (CDT)
From :-Yingdi
Subject :-hw3 1a.
Comments:- Does L(M)^R mean like the Rth power set of the language? I couldn't find an example of this syntax in the notes. Thanks.

Date Stamp :- Wednesday, October 02, 2002 at 22:03:06 (CDT)
From :-Tazeen
Subject :-Discussion session problem
Comments:- This is for the last two people in the discussion today.. we were solving a problem and doing it correctly too but not seeing it.. that happens after a couple of hours of automata theory :-D.
We had w = a^n b b a^n (where a^n means a to the n)
then we pumped down and got a^(n-p) b b a^n
p is greater than 0 and either odd or even.
if p is odd, the length of the string is odd and it's not in the language.
if p is even, there are fewer a's at the start of the string than at the end. If you divide the string in half, the b's will be in the first half.. so the first half of the string has fewer a's than the second half of the string.. so this string is not in the language either.
Since x y^0 z is not in the language, the language is not regular.

Date Stamp :- Wednesday, October 02, 2002 at 21:55:08 (CDT)
From :-Tazeen
Subject :-hw3 problem 2e
Comments:- in x#y, # is just like any other input alphabet, in this case it lets you know where x stops and y begins. so one of the strings in the language is 11#10010

Date Stamp :- Wednesday, October 02, 2002 at 21:45:32 (CDT)
From :-Sam
Subject :-hw 3, prob 2e
Comments:- What does x#y mean?

Date Stamp :- Wednesday, October 02, 2002 at 10:50:27 (CDT)
From :-Richard Crippen
Subject :-non-determinism
Comments:- When you have 2 different transitions with the same state/input pair, you effectively have to follow both paths when you simulate. Think about the visual Elaine did with the coins on the drawing to get an idea of what you need to do.

Date Stamp :- Tuesday, October 01, 2002 at 23:29:58 (CDT)
From :-B T
Subject :-Non Deterministic Machine
Comments:- Having more than one transition from one state of the same value is perfectly legal in a non deterministic machine. For example 2, x, 2 and 2, x, 5

Date Stamp :- Tuesday, October 01, 2002 at 23:12:17 (CDT)
From :-H.B.
Subject :-Nondeterminisim
Comments:- Is having two 'a' transitions leading from the same state acceptable input and indicative of really an Epsilon (non deterministic) or is that an input error?

Date Stamp :- Tuesday, October 01, 2002 at 11:40:56 (CDT)
From :-Tazeen
Subject :-epsilon vs empty set
Comments:- A FSM accepts {epsilon} if the start state is a final state or you can reach a final state from the start state by epsilon transitions.
For {}, the FSM does not accept anything, so it never reaches a final state. You could draw it as one initial non-final state.

Date Stamp :- Tuesday, October 01, 2002 at 00:41:39 (CDT)
From :-banka
Subject :-epsilon vs empty set
Comments:- what is the difference between the input string epsilon vs. the input "empty set"?

Date Stamp :- Monday, September 30, 2002 at 22:56:51 (CDT)
From :-Richard Crippen
Subject :-Re: Empty Set
Comments:- Your assumption should be correct. The machine you describe would indeed accept the empty set. It's the same as having a DFSM with the start state being a final state.

Date Stamp :- Monday, September 30, 2002 at 22:23:49 (CDT)
From :-Btazz
Subject :-Empty Set
Comments:- Assume we have a simple machine. Start State with two epsilon transition to two other states, both of which are final states. Am I correct in assuming that input as Empty Set does reach a final state and thus is accepted by the machine?

Date Stamp :- Monday, September 30, 2002 at 22:13:48 (CDT)
From :-Richard Crippen
Subject :-Re: Perl Hashing
Comments:- Thanks Will. I pretty much came to that conclusion myself after attempting every conceivable way. I think I found the only thing I don't like about Perl so far, but the string trick makes up for it.

Date Stamp :- Monday, September 30, 2002 at 21:52:14 (CDT)
From :-Will Natale
Subject :-Re: Perl Hashing
Comments:- Richard - I don't think you can use a list as a value of a hash..I ended up using strings instead, it's easy enough to split strings into lists when you need to using split()

Date Stamp :- Monday, September 30, 2002 at 21:26:01 (CDT)
From :-J. Wokaty
Subject :-
Comments:- I see it now. Thanks, Tazeen :)

Date Stamp :- Monday, September 30, 2002 at 19:19:12 (CDT)
From :-Tazeen
Subject :-Error in description for machine 5
Comments:- http://www.cs.utexas.edu/users/ear/cs341/project1tests.txt
The mistake is on the second line for the machine description, it's q1, q2, ..., q9, q19, q11.
It should be q9, q10, q11.

Date Stamp :- Monday, September 30, 2002 at 19:16:54 (CDT)
From :-Tazeen
Subject :-Machine 3
Comments:- That's an intentional error in the machine description. There's no way to tell if the start states are missing or the final states. Print out a message and exit (or whatever you're doing to handle error cases).

Date Stamp :- Monday, September 30, 2002 at 18:08:46 (CDT)
From :-J. Wokaty
Subject :-Error in def. of machine 5
Comments:- I got Tazeen's email about a state being incorrect--but I don't see the mistake anywhere. It's the test cases listed on Dr. Rich's site > link for projects, right??

Date Stamp :- Monday, September 30, 2002 at 16:13:12 (CDT)
From :-Richard Crippen
Subject :-re: Machine 3
Comments:- I could be wrong, but I assume the input for Machine 3 means that q1 is start and q3 is the sole final state, and someone just entered it wrong. (It does happen, on occassion)

Date Stamp :- Monday, September 30, 2002 at 16:10:10 (CDT)
From :-Richard Crippen
Subject :-hashing fun with perl
Comments:- I thought I'd throw this out there, since I saw a few people are using Perl. Is there any way to have a list as the value in an associative array? It's driving me crazy trying to get it. Thanks if y'all can help.

Date Stamp :- Monday, September 30, 2002 at 14:36:37 (CDT)
From :-Joe Wempe
Subject :-Machine 3
Comments:- On the definition of Machine 3, does q1, q3 repsent two start states and no final state. Or no start state two final states.

Date Stamp :- Monday, September 30, 2002 at 13:12:11 (CDT)
From :-Tazeen
Subject :-Re: What to turn in for project 1?
Comments:- Turn in everything that Dr. Rich has listed on the project 1 webpage. The final test cases are the only test cases for which you must turn in the output.

Date Stamp :- Sunday, September 29, 2002 at 23:56:32 (CDT)
From :-J. Wokaty
Subject :-What to turn in for project 1?
Comments:- I'm a little confused about what I'm supposed to turn in, although I know Rich's website gave a list of what we're supposed to turn. Are the final test cases the only set of test cases we need to turn in because I don't think I have the other set of test cases since I played around with those test cases and changed them?

Date Stamp :- Sunday, September 29, 2002 at 17:39:19 (CDT)
From :-Mustafa
Subject :-RE:DFSM starting state
Comments:- I asked Dr Rich about this issue. She said, in our definition, there is only one start state, but multiple start states for non-deterministic machines are fine also because of the epsilon transitions. So, it is fine to accept more than one start state if it is documented. But, I think, accepting one start state, and the rest as epsilon transitions will be more consistent.

Date Stamp :- Sunday, September 29, 2002 at 16:43:19 (CDT)
From :-Alvaro
Subject :-DFSM starting state
Comments:- I'm almost 100% sure that there's only one initial state in either case.

Date Stamp :- Saturday, September 28, 2002 at 23:13:01 (CDT)
From :-Jeff Wang
Subject :-DFSM starting state
Comments:- I am wondering if for a DFSM, we only have one start state while for a NDFSM, we have multiple start states. Am i correct in my approach, or can i stipulate that in my documentations?

Date Stamp :- Saturday, September 28, 2002 at 19:54:09 (CDT)
From :-Will Natale
Subject :-Re: Perl Reg. Expression
Comments:- Matt, check out this website: Substitution and Translation. That website has some nice overall tutorials for Perl, pretty much everything you need to write this program..Main site

Date Stamp :- Saturday, September 28, 2002 at 18:17:32 (CDT)
From :-Matt
Subject :-PERL Regular Expression
Comments:- How do you make a regular expression check the entire string for a pattern instead of just looking for the pattern once in the string? For example, I am trying to write something that makes sure the state input is in the form q1 q2 q3 and not like q1 4 c ... but when i try to make sure its q followed by a digit, it succeeds when finding it once instead of looking at the whole string for the pattern. Any help would be greatly appreciated. Matt

Date Stamp :- Saturday, September 28, 2002 at 16:31:38 (CDT)
From :-Will Natale
Subject :-RE: Why Perl?
Comments:- In response to Joe's question about Perl.. it's much easier to do text parsing than with C++, in fact the regular expressions used in Perl are alot like the ones we use in class. Alot of things are made easier (loose types, search&replace capability, simple arrays, etc) for example, here's a few lines of code that takes out all spaces, tabs, and C++ style comments from a file (I hope html works here):

open(file_input, "<whatever.txt"); # open file for input
while ($line = <file_input>)
{
  $line =~ s/[ \t]//g;  #take out tabs & spaces
  $line =~ s/\/\/.*//g; #take out comments //like this
}

As you can tell, some of the syntax is also similar to C/C++ (if,while,for,etc) so learning the language is easy..My completed project in Perl is a little under 300 lines of code.

Date Stamp :- Saturday, September 28, 2002 at 14:14:18 (CDT)
From :-Michael
Subject :-Input for NDFSM
Comments:- I'm currently working on a solution where I can take a transition relation that looks like for example: ({2 4},b,{2 5 7}) ({1 2 3},a,{3 5}) ({1},b,{2}) ..etc But this can be rewritten equivalenty with only 1 state in the first third of the tuple. And this would be very nice :) Does my program have to accept input where the first third of the tuple is a set of states? Thanks, Michael.

Date Stamp :- Saturday, September 28, 2002 at 12:44:13 (CDT)
From :-Joe Wempe
Subject :-Why perl?
Comments:- I am working on this in c++ and it is getting long. I am just wondering what can perl do that make this project so much shorter and easier.

Date Stamp :- Saturday, September 28, 2002 at 10:08:17 (CDT)
From :-Tazeen
Subject :-Project 1 input
Comments:- You can choose how your program reads the input.. just put it in the project documentation.
You're welcome :)

Date Stamp :- Friday, September 27, 2002 at 12:00:24 (CDT)
From :-Richard Crippen
Subject :-Project 1 input
Comments:- First of all, thanks for setting this up. How should we accept input for the project? Should it be from a file, from standard input, or do we get to choose? Thanks.

Date Stamp :- Thursday, September 26, 2002 at 11:44:16 (CDT)
From :-Tazeen
Subject :-errors in machine description for project 2
Comments:- If there is an error in the machine definition given to you, your program should print out a helpful error message and exit or ask for user to enter next input.. whatever you decide to do, put it in your documentation.

Date Stamp :- Thursday, September 26, 2002 at 11:42:11 (CDT)
From :-Tazeen
Subject :-{ }
Comments:- The finite state machine for { } would say no to everything.. so it would just be a start state that's NOT a final state..
A start state that is a final state accepts {epsilon}

Date Stamp :- Wednesday, September 25, 2002 at 13:45:07 (CDT)
From :-Chiu
Subject :-Definition 2 of proj1
Comments:- Hi Tazeen In definition 2 given in the proj, what is the start states and the end sates of the machine? There is only 1 line "q1,q5" instead of 2. Thanks Chiu

Date Stamp :- Tuesday, September 24, 2002 at 15:27:24 (CDT)
From :-arjun
Subject :-yes
Comments:- mustafa, i think there is because the start state is set to be a final state in our algorithm. thus for L={} it should work, i think?? i'm confused too.

Date Stamp :- Tuesday, September 24, 2002 at 14:38:04 (CDT)
From :-Mustafa
Subject :-{}
Comments:- A language L is accepted by a finite autamaton if the finite atuomaton says "YES" for every element of L, and says "NO" for non-elements. But what if L={}? Is there any finite automaton that accepts {}? Thanks.

Date Stamp :- Tuesday, September 24, 2002 at 10:50:57 (CDT)
From :-Tazeen
Subject :-HW 2 Problem 3
Comments:- step 3 in the algorithm that I posted earlier is wrong.. before reading the explanation think why....

If L = {}, then the 3rd step means that Pref(L)={epsilon}.. this is wrong. Pref(L)={}
Just remove the third step. If any string is accepted by the FSM for L, then the start state will be in the set of states that lead to a final state and will be marked final in step 2.
Sorry for any confusion.

Date Stamp :- Monday, September 23, 2002 at 22:59:27 (CDT)
From :-J. Wokaty
Subject :-
Comments:- Thanks, Tazeen :)

Date Stamp :- Monday, September 23, 2002 at 22:24:51 (CDT)
From :-Tazeen
Subject :-HW2 Problem 3
Comments:- It's a proof by construction.. so for Pref(L).. try this out.. draw a FSM for some L.. for example L = {ab, baa}.. now the Pref(L)={epsilon, a, ab, b, ba, baa}.. what you're trying to prove is that if a FSM exists for L, you can create an FSM for Pref(L).

So in your proof in the homework write down the steps that you would take to convert an FSM that accepts L to one that accepts Pref(L).

1. Figure out the states in the original FSM that are on the path to a final state.
You need to write down how you would do this.
Assume the original FSM has k states and E* is given to you. From each state try as input, strings of length 0 to k-1 and see if you land in a final state.. if you do then add the state you started from to the set of states that lead to a final state.
2. Mark all these states as final states.
3. Mark the start state as a final state.

This is your FSM for Pref(L). You have an algorithm for getting a FSM for Pref(L) from an FSM for L.

Date Stamp :- Monday, September 23, 2002 at 21:09:25 (CDT)
From :-Justin
Subject :-
Comments:- Thanks J. Wokaty, that was my guess.

Date Stamp :- Monday, September 23, 2002 at 21:07:20 (CDT)
From :-J. Wokaty
Subject :-HW2, Problem 3
Comments:- I don't think so, Justin. I think that 000 and 111 each have 2 pairs of the same string.

Date Stamp :- Monday, September 23, 2002 at 20:55:12 (CDT)
From :-Justin
Subject :-HW 2 Problem 1-e
Comments:- Should 000 or 111 be accepted by the machine?

Date Stamp :- Monday, September 23, 2002 at 20:47:59 (CDT)
From :-J. Wokaty
Subject :-HW2 Problem3
Comments:- Bah! I meant, how do you _show_ something like that? How should you start the proof for that?

Date Stamp :- Monday, September 23, 2002 at 20:38:26 (CDT)
From :-J. Wokaty
Subject :-Hw2, Problem 2
Comments:- I'm not exactly sure how to go about converting a deterministic machine to a nondeterministic one--or if my answers are even right--but this is how I started 2.2. First for accepting 101, I made 3 states with the transition 1, 0, 1. You do the same for 010. You connect the starting states of these with a starting state with epsilon transitions. (This is your actual starting state.) But you still need to account for both strings being in the input and adding a final state once both 101 and 010 have been accepted. Since you only want to know if 101 and 010 are in the input, you don't care if something "falls off a cliff."

Date Stamp :- Monday, September 23, 2002 at 20:27:21 (CDT)
From :-J. Wokaty
Subject :-HW2 Problem3
Comments:- BTaz, I might be misunderstanding you, but the problem's asking you to prove that if L is accepted by a finite automaton, then say, for pref(L), pref(L) is accepted by one as well--not necessarily the same finite automaton. What I'm wondering is, how do you should something like that?

Date Stamp :- Monday, September 23, 2002 at 18:44:45 (CDT)
From :-BTaz
Subject :-prefix, suffix
Comments:- on hw 2 #3 is it saying if we have a machine that only accepts, for example, aaab then we need to prove that any of the prefixes (E a aa aaa aaab) are accepted? Clearly they are not so I must be reading the question wrong.

Date Stamp :- Monday, September 23, 2002 at 18:17:07 (CDT)
From :-Dab
Subject :-NDFSM
Comments:- For Rich's Homework 2 #2, I can easily create the Deterministic machine, yet I cannot seem to figure out where to start to create a NonDeterministic one. How do you start out creating one of those? Any help would be appreciated.

Date Stamp :- Monday, September 23, 2002 at 13:38:01 (CDT)
From :-Tazeen
Subject :-HW2 Problem 2 b
Comments:- For 2b on HW2, 1010 should be accepted. For 1 g, it should accept 0 a's, 5 a's, 10 a's and so on.. so start with a FSM with 5 states with transitions on a from one to the other so it's a big loop of five states.. then each b is equal to two a transitions.. hope that helps.

Date Stamp :- Sunday, September 22, 2002 at 18:29:00 (CDT)
From :-J. Wokaty
Subject :-HW2 Problem 2.b
Comments:- On Problem 2.b for HW2, would 1010 be accepted by the machine? Also, anyone have any suggestions as to how I should attempt 1g? I haven't had much luck with it.

Date Stamp :- Tuesday, September 17, 2002 at 23:00:44 (CDT)
From :-Asraa
Subject :-
Comments:- Hi Tazeen. its okay, i asked Dr. Rich! Thanx. :-)

Date Stamp :- Tuesday, September 17, 2002 at 18:35:27 (CDT)
From :-Tazeen
Subject :-self assessment quiz
Comments:- Hi Asraa, I don't have a copy of the self assessment quiz. You'll have to tell me what question 8 is.

Date Stamp :- Monday, September 16, 2002 at 12:28:52 (CDT)
From :-Asraa
Subject :-self assessment quiz
Comments:- hey Tazeen, can u please tell me why the answer to question 8a) is 'no'? i thought it was 'yes'. Thanx! :-)

Date Stamp :- Monday, September 16, 2002 at 12:26:47 (CDT)
From :-
Subject :-
Comments:-

Date Stamp :- Monday, September 16, 2002 at 12:25:56 (CDT)
From :-Asraa
Subject :-
Comments:- hey Chiu, if u r talking about the practice quiz in the discussion section, then the answer to 8 is a). since the even ints can be both positive & negative, u can get a positive or negative even integer as a result of subtraction. hope that answers it.

Date Stamp :- Monday, September 16, 2002 at 12:25:30 (CDT)
From :-Tazeen
Subject :-Quiz question 8
Comments:- Thanks Chiu, don't know what I was thinking! The answer to question 8 is a, even integers are closed under subtraction.

Date Stamp :- Sunday, September 15, 2002 at 14:19:57 (CDT)
From :-Chiu
Subject :-Quiz Q8
Comments:- Hi. Does anybody know why the answer to q8 in the quiz is not (a)? Isnt the closure of even ints under subtraction even ints since 2m - 2n where m and n are ints is equal 2(m - n) which still gives an even int? Thanks

Date Stamp :- Thursday, September 12, 2002 at 10:46:41 (CDT)
From :-Tazeen
Subject :-7g
Comments:- xy is string concatenation. |xy| is the length of the concatenated string.

Date Stamp :- Thursday, September 12, 2002 at 10:45:16 (CDT)
From :-Tazeen
Subject :-Q5
Comments:- 5a) yes 5d) L1O is L1 concatenated with the empty set, which is the same thing as the cross product of the two sets.

Date Stamp :- Thursday, September 12, 2002 at 02:45:04 (CDT)
From :-ak
Subject :-7g
Comments:- In |xy|, is "xy" integer multiplication or string concatenation? Given the context of our current topic, Larry Wall would vote for the latter, but then the problem seems suspiciously trivial. If it isn't, do || and "even" mean string length or absolute value? Even Larry Wall wouldn't approve of this typing strategy, I'm sure.

Date Stamp :- Thursday, September 12, 2002 at 01:02:52 (CDT)
From :-
Subject :-Q5
Comments:- 5a) L1* is the Kleene star of L1 right? 5d) What is L1O? Is it (L1 n O)? (where O is the null set)

Date Stamp :- Tuesday, September 10, 2002 at 10:52:53 (CDT)
From :-Tazeen
Subject :-Question 7e
Comments:- Hi Chiu, "10001" is considered as two pairs of consecutive 0's. 11 can come before or after 00.. so you have to take care of all the cases you listed. You're welcome! Tazeen

Date Stamp :- Tuesday, September 10, 2002 at 00:49:20 (CDT)
From :-Chiu
Subject :-Question 7e
Comments:- Hi Tazeen.This involves Q7e. 1.Say we have a sting "10001".Now do we consider this as 1 pair of consecutive 0s followed by a 0 or is it 2 pairs of consecutive 0's ? 2.Do we have to take care of strings like "...0011...." , "......1100..." . "...00..11.." , "....11...00...." or do we take it as "00" always appear before"11"? Thanks Chiu

Date Stamp :- Monday, September 09, 2002 at 15:49:52 (CDT)
From :-Tazeen
Subject :-Regular Expressions
Comments:- Yes, you're right Alvaro. Regular Expressions are defined in Lecture Notes 1 Page 4.

Date Stamp :- Sunday, September 08, 2002 at 21:49:08 (CDT)
From :-Alvaro Peluffo
Subject :-Regular Expressions
Comments:- On page 4 of the packet in the Lecture Notes section, there's a description of regular expressions; I think we can only use the things that appear on that page, not S -> (S), etc? Is that right Tazeen?

Date Stamp :- Saturday, September 07, 2002 at 15:11:36 (CDT)
From :-Scott Stinson
Subject :-Problem 7: Regular Expressions
Comments:- When we are asked for regular expressions, can we write something like S -> 0 S -> 1A or do we have to write something like L = { x -> (a,b) | ?

Date Stamp :- Thursday, September 05, 2002 at 11:08:34 (CDT)
From :-Tazeen
Subject :-Problem 3
Comments:- Check out the solution to question 10 on practice homework 1 in the course packet.

Date Stamp :- Wednesday, September 04, 2002 at 20:21:05 (CDT)
From :-J. Wokaty
Subject :-Problem 3
Comments:- Is problem 3 asking us to state everything the set is closed on if it is not closed under an operation? For example, if the negative integers aren't closed under divison, then we have to list what negative integers are closed under? Maybe I misunderstood the question.

Date Stamp :- Monday, September 02, 2002 at 20:45:29 (CDT)
From :-Alvaro Peluffo
Subject :-2 raised to a set
Comments:- 2 raised to a set means the power set of that set; which is all posible sets that can be formed with the members of that set. For example, if the set is {1,2}, the power set is {{},{1},{2},{1,2}}.

Date Stamp :- Sunday, September 01, 2002 at 12:55:46 (CDT)
From :-Pete Forsberg
Subject :-Review question
Comments:- I'm currently working on Homework one and it has been a while since I worked with sets and forgot some things. What does 2 raised to a set mean? Also on problem 2 e) I'm not sure how to prove this. Thanks in advance.

Date Stamp :- Tuesday, August 27, 2002 at 17:23:02 (CDT)
From :-Tazeen
Subject :-Welcome
Comments:- Welcome to the CS341 Discussion Forum. It is designed for students to communicate with each other. This is your forum, use it.