Discussion Forum
[
Home |
Discussion |
Post
]
Date Stamp :- Friday, December 12, 2003 at 09:54:28 (CST)
From :-Tazeen
Subject :-Re: cheet sheet
Comments:- 4x6 index card (anything smaller is fine too!)
Date Stamp :- Thursday, December 11, 2003 at 23:48:28 (CST)
From :-dgardner@cs.utexas.edu
Subject :-cheet sheet
Comments:- What size cheet sheet may we use on the final: 3 X 5 or 81/2 X 11?
thanks,
dustin
Date Stamp :- Monday, December 08, 2003 at 22:50:37 (CST)
From :-Tazeen
Subject :-Re: Time
Comments:- Dr. Rich didn't have office hours on Monday, she has them Tuesday morning 9:30 - 11 in her office
Date Stamp :- Monday, December 08, 2003 at 11:22:15 (CST)
From :-Mike
Subject :-Time
Comments:- What time did Dr. Rich say she was going to be at her office on Monday evening?
Date Stamp :- Tuesday, December 02, 2003 at 10:07:29 (CST)
From :-Tazeen
Subject :-RE: Rice's theorem
Comments:- You have to show that the domain of the property is the set of RE languages, so putting it in english, the property should be about something that can be semi-decided by a turing machine, such as strings in a language. Does that make it any clearer? :-) Try reading Supplementary Materials, RE Languages, Turing Machines, and Decidability page 7. It's in the very end of Dr. Rich's notes.
Once you get the hang of it, it's very easy to use. That's why Dr. Rich's exams usually specify NOT to use Rice's theorem.
Date Stamp :- Thursday, November 27, 2003 at 18:43:31 (CST)
From :-craig
Subject :-Rice's theorem
Comments:- how do we show if a property is in the domain of RE languages?
Date Stamp :- Monday, November 24, 2003 at 19:53:07 (CST)
From :-Tazeen
Subject :-Re: EQ
Comments:- I meant EQ for DFAs as opposed to for TMs or PDAs.
Date Stamp :- Monday, November 24, 2003 at 19:24:34 (CST)
From :-Austin
Subject :-EQ
Comments:- Tazeen, you said EQ(DFA) does that mean that EQ takes 2 DFS'a because it doesnt make sence to take just one.
Date Stamp :- Monday, November 24, 2003 at 17:19:26 (CST)
From :-Tazeen
Subject :-RE: HW 11: 3-5
Comments:- If Dr. Rich has shown you proofs in class that Empty(DFA) and EQ(DFA) are recursive, then you can assume you have those TMs. Otherwise you have to construct them.
Date Stamp :- Monday, November 24, 2003 at 17:12:47 (CST)
From :-Tazeen
Subject :-Re: HW11, #2
Comments:- Look at Homework 20 , question 2 in Dr. Rich's Notes.
Date Stamp :- Monday, November 24, 2003 at 14:42:06 (CST)
From :-Nate
Subject :-reposting definitions
Comments:- Those came out in weird format-should be E={"A"|A is a DFA and L(A)=null set} and EQ={"A,B"|A and B are DFAs and L(A)=L(B)}
Date Stamp :- Monday, November 24, 2003 at 14:40:19 (CST)
From :-Nate
Subject :-HW 11: 3-5
Comments:- Similar to when we were doing decision procedure homeworks, can we assume we have two TMs E (decides emptiness), EQ (decides equivalency) where E={A|A is a DFA and L(A)=null set} and EQ={A,B|A and B are DFAs and L(A)=L(B)} or do we need to construct these independently if we're using them. Thanks.
Date Stamp :- Sunday, November 23, 2003 at 22:58:52 (CST)
From :-Lee
Subject :-HW11, #2
Comments:- I was curious on how to work with functions with a Grammar. I believe that we are to define the format of the input, and the rules of the grammar transform the input into the desired output, but wasn't sure how to deal with things such as the start state. Does the whole input act as a single non-terminal? I was just a bit confused on how to deal with this.
Date Stamp :- Thursday, November 20, 2003 at 00:37:33 (CST)
From :-Kevin
Subject :-RE: symtab.c
Comments:- symtab.c and symtab.h are posted under the announcements from October 13 on Tazeen's page.
Date Stamp :- Tuesday, November 18, 2003 at 13:15:13 (CST)
From :-Tazeen
Subject :-RE: still dropping it in hw box in taylor right?
Comments:- Yes, use the drop box in Taylor to turn in the project. If you already handed it to Dr. Rich, that's fine. It's due at 3:00 pm. That's when I'll collect them.
Date Stamp :- Tuesday, November 18, 2003 at 12:25:59 (CST)
From :-Jimbo
Subject :-still dropping it in hw box in taylor right?
Comments:- just verifying we turn in this project in the hw dropoff in the breezeway in taylor like the last project right-and it's due at 3pm right-the projects webpage says projects are due at 4pm but the project itself says 3pm so 3pm's the due date right? Thanks.
Date Stamp :- Tuesday, November 18, 2003 at 10:59:41 (CST)
From :-Tazeen
Subject :-RE: if statements
Comments:- If you have input of the form:
if false then 4
It's your decision what you want it to return, 0 is fine.
Date Stamp :- Tuesday, November 18, 2003 at 10:57:59 (CST)
From :-Tazeen
Subject :-Re: Proj2 Question 11
Comments:- Hi Mike, I'm not sure if I got your question, it may be that all the characters didn't get printed. You're asking how to implement term op term? One way to do it is to implement it similar to the implementation for + and -. Maybe the question had to with OR and AND. There's no OR operator in C, it's ||, does that help?
Date Stamp :- Tuesday, November 18, 2003 at 10:52:06 (CST)
From :-Tazeen
Subject :-RE: Project4-problem 4
Comments:- Different trace is fine if it's just that the numbers of the states are different. That just depends on what order the rules were written on in your expr.y and also which version of lex and yacc you're using, if you're working on Sun or Linux, etc.
Date Stamp :- Tuesday, November 18, 2003 at 10:47:22 (CST)
From :-Tazeen
Subject :-yywrap
Comments:- Don't need to change anything in yywrap to read in multiple lines of input, just change your grammar, add rules to Line : ...
Date Stamp :- Tuesday, November 18, 2003 at 04:11:21 (CST)
From :-Rager
Subject :-Post b4 mine
Comments:- pretty sure that's outside of what they're asking us, as they seem to be only asking to allow single statement inputs
Date Stamp :- Tuesday, November 18, 2003 at 00:59:26 (CST)
From :-John
Subject :-if statements
Comments:- so let's say we have:
a:=2
b:=4
if a=3 then if b=4 then 5 else 6+8
The first boolexp is false, but there is no else, so what value do you return for the expression? 0? false? value of a?
Date Stamp :- Monday, November 17, 2003 at 23:24:13 (CST)
From :-Mike
Subject :-My last post
Comments:- I guess this forum doesn't like the chevron characters.
Date Stamp :- Monday, November 17, 2003 at 23:22:43 (CST)
From :-Mike
Subject :-Proj2 Question 11
Comments:- For the BE -> temp op temp, I keep getting a parse error, if I hardcode the op, I don't get it, but I can't figure what variable declaration to use to get op returned correctly from the op-> < | <= ... part.
{$$ = $1 < $3;} gives the right answer, but {$$ = $1 $2 (or ) $3;} both yield parse errors.
Anyone have any suggestions for this part?
Date Stamp :- Monday, November 17, 2003 at 22:32:24 (CST)
From :-Anh
Subject :-Project4-problem 4
Comments:- Hey, for the system trace did you guys have it different than the one Dr. Rich said you will get? If so, why? How to fix it?
Date Stamp :- Monday, November 17, 2003 at 19:27:11 (CST)
From :-Gaurav
Subject :-Proj2
Comments:- Does any one know what yywrap() is supposed to be doing...Do we have to use it to take the input in again?
Date Stamp :- Monday, November 17, 2003 at 10:54:12 (CST)
From :-Tazeen
Subject :-RE: Assignment operator
Comments:- It's up to you.
Date Stamp :- Monday, November 17, 2003 at 08:11:22 (CST)
From :-John
Subject :-Assignment operator
Comments:- Hi,
For the assignment operator, are we supposed to assign anything to yyval? ie, would a:=5
return the value of a (5), or true (sucessfull assignment), or nothing?
Thanks,
John
Date Stamp :- Sunday, November 16, 2003 at 17:46:29 (CST)
From :-Kevin
Subject :-RE: symtab.c
Comments:- symtab.c and symtab.h are posted under the announcements from October 13 on Tazeen's page.
Date Stamp :- Sunday, November 16, 2003 at 17:21:46 (CST)
From :-Ben
Subject :-symtab.c
Comments:- I can't seem to locate this simtab.c file. Where is it supposed to be and how do we use it? This part of the project is killing me!
Date Stamp :- Wednesday, November 12, 2003 at 10:21:16 (CST)
From :-Tazeen
Subject :-RE: Project 2, Part II, #12
Comments:- It's up to you to decide what you want to return. 0 would be fine.
Date Stamp :- Tuesday, November 11, 2003 at 17:16:19 (CST)
From :-Grace
Subject :-Project 2, Part II, #12
Comments:- On the part "S -> if BE then S", if BE is not true, what do we return? nothing? zero? Please help! Thanks!
Date Stamp :- Sunday, November 09, 2003 at 22:12:05 (CST)
From :-Craig
Subject :-project 2 part 2 10.
Comments:- Is this supposed to ask for multiple lines of input? How is this accomplished? The instructions, reference manual, and posts on here aren't inadequately clear enough to accomplish this. I tried adding yyclearin; to my expr line in Line, all this did was print out the answer, go down a line, appear to take input which always returns a syntax error on whatever it is.
What are we supposed to be doing?
Date Stamp :- Saturday, November 08, 2003 at 13:17:55 (CST)
From :-Tazeen
Subject :-Hand trace
Comments:-
Partial y.output
Worked example
Date Stamp :- Friday, November 07, 2003 at 13:18:45 (CST)
From :-Tazeen
Subject :-RE: proj 2 question 4
Comments:- I'll try to post a more detailed example soon, but have to go to class right now. In the meanwhile, try reading the reference manual.
Date Stamp :- Friday, November 07, 2003 at 13:12:30 (CST)
From :-Tazeen
Subject :-RE: proj 2 question 4
Comments:- Different people may get different state numbers. It depends on which rule is written first, which version of lex and yacc you're using etc. Someone else's state 4 may be your state 3. As long as every time they get a 4 and you get a 3, you probably have it right.
Date Stamp :- Thursday, November 06, 2003 at 13:18:06 (CST)
From :-Tazeen
Subject :-RE: expr.y
Comments:- Yes, you are supposed to get the 4 shift/reduce conflicts in the beginning. The project asks you to change the rules later.
Date Stamp :- Wednesday, November 05, 2003 at 23:25:48 (CST)
From :-Craig
Subject :-proj 2 question 4
Comments:- I dont get what $(0)4(2) means. Is this saying after shifting 4 onto the stack it should be in state 2? But the y.output has no way to get to state 2 from state 0 unless you've shifted a ( onto the stack.
Then how does it go from $(0)4(2) to $(0)expr(5)?
Date Stamp :- Wednesday, November 05, 2003 at 20:54:13 (CST)
From :-Craig
Subject :-expr.y
Comments:- Are we supposed to get the notice "conflicts: 4 shift/reduce" when compiling expr.y with yacc? It still generated the tab file.
I had to retype the file by hand to get it to work and i'm pretty sure I did it right.
Date Stamp :- Tuesday, November 04, 2003 at 22:31:33 (CST)
From :-John
Subject :-Midterm 2
Comments:- Hey, I was just curious how you all did on the second midterm? What problems do you think you had the most trouble with/missed?
I had the most trouble with the decision procedure questions.
Date Stamp :- Thursday, October 30, 2003 at 16:21:35 (CST)
From :-Tazeen
Subject :-Project 2 Part II -- Post 2
Comments:-
3. To be able to return identifiers, lex should be able to return strings
instead of just numbers.
In expr.y, where you've added int yydebug=1, in that area add the
following line:
#undef YYSTYPE
Before %token .. add the following:
%union {
char name[21];
int val;
}
you've just redefined the type of yylval. So everytime you were assigning
anything to yylval, you have to rewrite yylval to yylval.val in expr.l
In expr.y everywhere you were using $$ or $1, rewrite it as $$.val or
$1.val on Sun ($<val>$ or $<val>1 syntax if you're
using Linux).
Make sure everything still works
4. In expr.l add the rule for identifier
[A-Za-z][A-Za-z0-9_]* {strncpy(yylval.name, yytext, 20); return (IDENT);
This is copying 20 characters from yytext to yylval.name. I'm making the
assumption that the maximum length of your identifier will be 20.
Add %token(IDENT) to expr.y
In the rules if have to use the string, it would be as $1.name
5. In expr.y #include "symtab.h" in the same area where you have int
yydebug=1;
6. use the functions in symtab.h to maintain the symboltable.
You'll probably only be using setsymtab and getsymtab
Now when you compile something, do it like this
lex expr.l
yacc expr.y
cc -c y.tab.c symtab.c
cc y.tab.o symtab.o
Date Stamp :- Thursday, October 30, 2003 at 16:16:15 (CST)
From :-Tazeen
Subject :-Project 2 Part II -- Post 1
Comments:-
You need to be able to make assignments to variables and be able to keep
their values so that you can use the variables later.
You have to do the following:
1. Your program is supposed to be able to return from an incorrect input
in Part I ques 7.
Make sure it also returns to take another input from a
correct input. You need to make additions to the rule Line : expr, similar
to the rule Line : error ...
2. You do want it to be able to exit. if the user types quit the
program exits. Make sure you add quit to expr.l. Have lex return the token
QUIT, (similar to it returning NUMBER), add %token QUIT to expr.y. add the
rule Line: QUIT {printf("bye!\n");} ; to expr.y
Date Stamp :- Thursday, October 16, 2003 at 10:47:10 (CDT)
From :-Tazeen
Subject :-Re: HW6 #3d
Comments:- The language is a binary_number#next_binary(reversed). So some strings in the language are 0#1, 1#01, 10#11, 11#001, 100#101, 101#011
Hints:
> Work from the outside in.
> The only string that starts with a 0, is 0#1.
> All other strings start and end with a 1.
> For strings that start and end with a 1, there are two cases around the #. Either the first binary number ends with a 0 or a 1.
> If it ends with a 0, then the first and last character are 1's. Working your way towards the center, if there's a 0 on the left of the #, there's a 0 on the right, same for 1's. The center of the string looks like 0#1.. e.g. 110100#101011.
>If the first binary number ends with a 1. Then you have two cases. Either the first binary number is all 1's, or it has a 0 somewhere in the string.
>If the first binary number is all 1's, then the string after the # is going to be the same number of 0's followed by a 1. Ex. 11#001.
>If the first binary number ends with a 1 and has a 0 somewhere in the strings. It's going to start and end with a 1. It's going to have the same characters on both sides until you get a 0 on the left, that will be matched by a 1 on the right side. after such a 0, there will only be 1's on the left side and 0's on the right side, the center will be 1#0. Ex. 101011#001101
Hope that helps.
Date Stamp :- Thursday, October 16, 2003 at 09:19:35 (CDT)
From :-John
Subject :-HW6 #3d
Comments:- I've spent way too much time on this problem and I can't seem to grasp the pattern for determining the grammar. Any hints?
Date Stamp :- Monday, October 06, 2003 at 19:23:19 (CDT)
From :-Tazeen
Subject :-Re: Midterm 1
Comments:- You need to study everything for regular languages. Dr. Rich told me she started Context Free Languages on Thursday, that will not be covered on midterm 1.
As far as state minimization goes, she said you have to know about tilde L and Myhill-Nerode, but since she skipped the algorithm to do the actual minimizations, you don't have to know that.
Date Stamp :- Monday, October 06, 2003 at 15:37:10 (CDT)
From :-Minh
Subject :-RE Midterm 1
Comments:- Except for the state minimization right?
Date Stamp :- Friday, October 03, 2003 at 18:05:20 (CDT)
From :-Tazeen
Subject :-Re: Midterm 1
Comments:- Anything she teaches until the exam, including on Tuesday morning could be on the midterm.
I would encourage you to go to class on Tuesday, she has a tendency to go over some concept that's going to somehow be relevant in the exam in the class that morning, even if it's not directly obvious to you during class.
Maybe it'll be some function or language that she uses as an example, that may show up in the exam too.
Ofcourse, she may decide not to do that this semester :-)
Date Stamp :- Friday, October 03, 2003 at 14:38:39 (CDT)
From :-Craig Washburn
Subject :-Midterm 1
Comments:- Will the material on HW5, and the 'nice' stuff handed out be on the exam?
Date Stamp :- Thursday, October 02, 2003 at 11:02:24 (CDT)
From :-Tazeen
Subject :-Re: HW 5 - #2a
Comments:- The # is just a character in your input. It's being used as a place holder so you can tell where x ends and y begins.
So your input would be of the form: 101#10
Date Stamp :- Thursday, October 02, 2003 at 01:13:01 (CDT)
From :-David Rager
Subject :-HW 5 - #2a
Comments:- What does the "x#y" mean again please?
Date Stamp :- Wednesday, October 01, 2003 at 11:38:46 (CDT)
From :-Tazeen
Subject :-Message from Dr. Rich
Comments:- Exam will be held next Tuesday, Oct. 7, from 5-7 and from 7-9,
both in BUR 212. You can come to whichever time is more convenient.
If you have a conflict (such as a class from 6-8), we can arrange a makeup
on Wednesday morning but you must tell me this week and schedule a time.
If you take the makeup, you'll be asked to sign a statement that you did
not talk to anyone about the exam after it was given on Tuesday
evening.
You may bring one 4 x 6 index card of notes to the exam. You may hand write the notes or print them out using any font you can read. You may use
the front and back of the card. There will also be a single card allowed
for midterm 2 and the final.
The exam will cover everything we have covered on regular languages. The
homeworks are a good guide for what is important.
Luay will run a review session on Monday night. Try to go prepared to ask
questions.
If you want to make sure that no one else sees your grade on the exam, please bring a 9 x 12 envelope to the exam. Place your exam in the envelope and write your name on the outside. Don't seal the envelope. After we grade the exam, we will return it to the envelope and seal it.
Date Stamp :- Wednesday, October 01, 2003 at 11:30:16 (CDT)
From :-Tazeen
Subject :-Message from Luay -- Part 3
Comments:- 6. I do *not* intend to provide written solutions to these problems.
7. Finally, remember: I'm not on the staff of this course. Therefore, I
do NOT (make sure you read and understand the "negation" in this
sentence) hold office hours.
All questions/clarification/suggestions regarding the handout are more than welcome. I sit in ACES 3.304; you're welcome to stop by with "nice" questions, but be prepared also to hear (very often) "I don't have time now"!
See you on Monday.
Luay
Date Stamp :- Wednesday, October 01, 2003 at 11:29:44 (CDT)
From :-Tazeen
Subject :-Message from Luay -- Part 2
Comments:- 3. This is a *review* session! I am not going to lecture, and will assume
you know the definitions, lemmas and theorems.
4. The set of problems that I posted may contain some problems on material
that your instructor didn't teach or isn't required of for the exam.
If you attended class AND you were awake, you should be able to tell
which problems fall in this category and ignore (unless you haven't had
enough of Automata Theory and would like to do extra work!!!)
5. Please, please, please, study the material, and work on as many
problems as you can before the review session. That way we can make the
most of it, and will be more helpful to all of you. If some students
come unprepared, and they start asking trivial/simple questions,
that will defeat the purpose of the review session. I don't mind
answering trivial questions, but remember that the majority of students
come to the review session prepared and to clarify "real" issues.
Also, for the other extreme: I LOVE challenging questions and problems,
but for those who want such problems, I'd like to say that this is not
going to be the purpose of this session. We'll be there to clarify thru
examples what you learned in class, and to help you better prepare you
for the exam.
Date Stamp :- Wednesday, October 01, 2003 at 11:28:38 (CDT)
From :-Tazeen
Subject :-Message from Luay
Comments:- Hi All,
The review session for the first midterm is going to be held on Monday, Oct 6, from 6:00 to 10:00 (if more time is needed, and there is energy left, we can stay longer). The session will be held in TAY 2.006.
I have prepared a set of practice problems; it's posted at
http://www.cs.utexas.edu/users/nakhleh/1st_midterm_review_fa03.pdf
A few important points:
1. some of the problems are *challengin*. Do NOT panic -- just ignore them
if you are not interested. From previous experience, there are a few
students who like to work on more challenging problems than what they
see on the homework. We will not discuss those problems in the review
session. If any of you is interested in solving them, or would like to
verify their solutions, you can talk to me anytime.
2. The objective of the review session is to answer your questions. So,
come prepared with questions and problems.
Date Stamp :- Tuesday, September 30, 2003 at 13:00:21 (CDT)
From :-Tazeen
Subject :-Re: Proj1
Comments:- Yes, Dr. Rich said it's ok for you to post your results on the input.
Date Stamp :- Monday, September 29, 2003 at 18:00:18 (CDT)
From :-Austin
Subject :-Proj1
Comments:- Are we allowed to post our results on the input to check for continuity against our peers?
Date Stamp :- Monday, September 29, 2003 at 01:56:08 (CDT)
From :-Kevin
Subject :-RE: epsilon question
Comments:- I think it would accept epsilon. The intial set of states would be {q0, q1, q2}. Since the only input character is epsilon, the machine does nothing and ends up in states {q0, q1, q2}. So, the machine accepts.
Date Stamp :- Sunday, September 28, 2003 at 20:16:11 (CDT)
From :-Craig
Subject :-epsilon question
Comments:- Suppose you have a machine of 3 states q0, q1, q2. q0 is initial and q1 and q2 are final. suppose q0 has epsilon transitions to q1 and q2, but q0 is *not* final. If the only symbol in the sequence is epsilon, would this be valid or invalid?
Date Stamp :- Sunday, September 28, 2003 at 14:08:26 (CDT)
From :-Atri
Subject :-Machine errors
Comments:- Make sure that your simulator reconizes the errors in machine description and does not fail: so either it spits out an error message or it assumes something and goes on with the simulation. In either case be sure to document it in your user documentation.
Date Stamp :- Sunday, September 28, 2003 at 13:51:41 (CDT)
From :-Lloyd
Subject :-Re: another error
Comments:- I assume that if it goes to some state that's not a member of my list of states, that the transition is invalid, which makes the definition of the machine kind of ambiguous, so I skip it and its input and move onto the next machine definition.
Date Stamp :- Sunday, September 28, 2003 at 12:34:49 (CDT)
From :-Craig
Subject :-another error
Comments:- in machine 4 the last transition goes to a non-existant state. is it alright just to spit out an error and not run that machine and those sequences at all? or is q4 just missing from the states list.
Date Stamp :- Sunday, September 28, 2003 at 12:17:07 (CDT)
From :-Craig
Subject :-doh
Comments:- obviously you can't have 2 initial states, so it looks like its missing its initial state - do we assume it to be q1?
Date Stamp :- Sunday, September 28, 2003 at 12:16:10 (CDT)
From :-Craig Washburn
Subject :-proj1 machine 3
Comments:- machine 3 appears to be missing either final states or an initial state in its definition
Date Stamp :- Wednesday, September 24, 2003 at 14:28:19 (CDT)
From :-Tazeen
Subject :-Re: HW
Comments:- No, it's not wishful thinking. There's really no homework due till the 2nd :-)
Date Stamp :- Wednesday, September 24, 2003 at 12:54:04 (CDT)
From :-
Subject :-HW
Comments:- Is it possible that we have no homework due tomorrow? Am I imagining things?
Date Stamp :- Saturday, September 20, 2003 at 13:04:35 (CDT)
From :-Tazeen
Subject :-RE: Proj 1
Comments:- So for project 1, you read in descriptions for FSMs. At a minimum, you're required to detect that there is a problem if the description is invalid, you don't have to fix it (unless you want to).
If there is something wrong with the description of a FSM, you may decide to print out an error message and just skip that FSM. If the description is valid and you create the FSM but the characters in an input string to the FSM are not part of the alphabet.. then you can decide to print an error message and ignore that whole string... or do something else.
Just remember to document what you decide to do on specific kind of errors
and turn that in with the project.
Date Stamp :- Friday, September 19, 2003 at 17:14:01 (CDT)
From :-Rager
Subject :-Proj 1
Comments:- "(3) Write a simulator that will not crash even if the input it receives is not legal (e.g., there is a transition that involves a state that is not part of the machine). Make reasonable decisions about what should happen given illegal input and document those decisions. At a minimum, you must output some sort of error message informing the user of the problem. "
If we find duplicate or impossible data, can we just output the line of input that has a problem and then ignore that specific problem? Almost obviously, we wouldn't ignore the whole line, unless the whole line is invalid.
Date Stamp :- Wednesday, September 17, 2003 at 22:32:15 (CDT)
From :-David Rager
Subject :-Thanks
Comments:- Cool. Thanks man! :)
Date Stamp :- Wednesday, September 17, 2003 at 22:21:30 (CDT)
From :-Kevin
Subject :-RE: Equals sub 3
Comments:- That's the equivalence mod operator. It basically means (in this case), (n % 3) == (m % 3).
Date Stamp :- Wednesday, September 17, 2003 at 22:10:55 (CDT)
From :-Kevin
Subject :-RE: HW #3/ Q3
Comments:- I think you're slightly misunderstanding the question. It says that if an FSM accepts a language L, then there is some other machine that will accept Pref(L). Our job is to design an algorithm to take the original machine and turn it into one that accepts Pref(L).
For example, if L = {aba}, then Pref(L) = {e, a, ab, aba}. So, we'd take the machine that accepted "aba" and change it so that it accepted "e", "a", "ab", and "aba" (where e is epsilon).
Hope this helps.
Date Stamp :- Wednesday, September 17, 2003 at 22:04:32 (CDT)
From :-David Rager
Subject :-Equals sub 3
Comments:- What does =3 (where the = is triple equal and the 3 is subscript) mean?
Date Stamp :- Wednesday, September 17, 2003 at 20:59:19 (CDT)
From :-David Rager
Subject :-HW #3/ Q3
Comments:- I read the previous post about this question and looked at the lecture notes, but I'm still confused :\ (at least on Pref(L) and Suf(L)).
If "aa" is a word in my language, a prefix of "aa" is "a." But, what if my language only consists of words that are even in length? Then, not every prefix of every word in L is in the Language.
Maybe I just have what L represents confused. How does one find the prefix of a language?
Any help offerred is appreciated :)
Date Stamp :- Wednesday, September 17, 2003 at 11:04:47 (CDT)
From :-Tazeen
Subject :-Re: HW 3 Question 4
Comments:- You don't have to draw it, writing down the s' etc. completely defines a DFSM.
Date Stamp :- Tuesday, September 16, 2003 at 21:38:04 (CDT)
From :-Craig
Subject :-HW 3 Question 4
Comments:- Do we need to draw the DFSM, or just show E, s', delta', k' and F'?
Date Stamp :- Tuesday, September 16, 2003 at 10:15:47 (CDT)
From :-Tazeen
Subject :-RE: HW 3 question 3
Comments:- Ignore the part where it says "Define the following languages", the set descriptions are already given to you.
For the part "Show that if L is accepted by some FSM, then so is each of the following:", it is similar to Lecture notes 8 page 2. Assume you have a FSM for L, and specify what changes you would make to it for it to accept the given language.
What may help is if you pick a particular L, draw its FSM, then change it to accept the Pref(L) or Suf(L) or Max(L). Do this to get a general idea of what you need to do, then write down this general
algorithm that would work on the FSM for any L.
Date Stamp :- Monday, September 15, 2003 at 17:43:03 (CDT)
From :-Craig
Subject :-HW 3 question 3
Comments:- I don't understand Question 3 on HW3 - what are we supposed to be finding/doing? Are there any similar examples somewhere?
Date Stamp :- Thursday, September 11, 2003 at 23:20:25 (CDT)
From :-Tazeen
Subject :-Re: Packet HW 4
Comments:- Ok. I'll ask Dr. Rich what she wants to do about that. Thanks for letting me know.
Date Stamp :- Thursday, September 11, 2003 at 22:50:23 (CDT)
From :-Craig
Subject :-Packet HW 4
Comments:- On mine the solutions to questions 10 through 14 are missing also
Date Stamp :- Thursday, September 11, 2003 at 22:22:23 (CDT)
From :-Tazeen
Subject :-Re: Course packet HW solutions
Comments:- It's not available online. Just scanned through the homework solutions, homework 4 question 4 is not printed right. Maybe I can post the solution on my website. Is that the only one?
Date Stamp :- Thursday, September 11, 2003 at 21:36:12 (CDT)
From :-Craig Washburn
Subject :-Course packet HW solutions
Comments:- Are the solutions for the HW's in the course packet available online anywhere? The print on my copy is poor and some of the FSM's are totally illegible
Date Stamp :- Wednesday, September 10, 2003 at 23:27:45 (CDT)
From :-Tazeen
Subject :-Rational Numbers
Comments:- The set of all rational numbers is countably infinite.. here's
a proof
Date Stamp :- Wednesday, September 10, 2003 at 16:45:31 (CDT)
From :-Tazeen
Subject :-Re: Max and mix
Comments:- L = { a, bb, bba, bbaabb}
Max(L) = { a, bbaabb}
Mix(L)
= {bb, bbabba}
For Max(L), look at each string in L. If you can
concatenate anything from Sigma * to its right side such that the
resulting string is in L, then it's not in Max(L), otherwise it is in
Max(L).
So in the example, the first string is a. You can't
concatenate anything to its right side to get another string in L, so it
is in Max(L).
The second string is bb, you can concatenate a to its
right side to get bba, or concatenate aabb to its right side get bbaabb,
so for either of those reasons, it is not in Max(L).
The third string
is bba, you can concatenate abb to its right side to get bbaabb, so it is
not in Max(L).
The fourth string is bbaabb, you can't concatenate
anything on its right side to get another string in L, so it is in
Max(L).
For Mix(L), look at each even length string in L. Reverse its
last half.
The first even length string in L is bb. Its last half is
b, reverse of b is b. So Mix(L) has bb.
The second even length string
in L is bbaabb. It's last half is abb, if you reverse it, it is bba, so
bbabba is in Mix(L).
Date Stamp :- Wednesday, September 10, 2003 at 15:05:20 (CDT)
From :-Craig
Subject :-Max and mix
Comments:- I don't understand what max and mix are doing. Does anyone have it in english, or examples of how these are supposed to work?
Date Stamp :- Wednesday, September 10, 2003 at 14:26:18 (CDT)
From :-Tazeen
Subject :-Re: Question 2c
Comments:- The wording is correct
Date Stamp :- Wednesday, September 10, 2003 at 03:29:57 (CDT)
From :-Russell
Subject :-Question 2.c.
Comments:- Should this question read, "Every countably infinite language..." or is the wording correct?
Date Stamp :- Monday, September 08, 2003 at 16:29:18 (CDT)
From :-Tazeen
Subject :-Consecutive Pairs
Comments:- Note that 000 is two pairs of consecutive 0's.
Date Stamp :- Monday, September 08, 2003 at 16:27:25 (CDT)
From :-Tazeen
Subject :-RE: hw2--Q5
Comments:- Mix(L) = { w : There exist x, y, z elements of L, x = yz, |y|=|z|, w =y z^R}
Date Stamp :- Monday, September 08, 2003 at 16:12:49 (CDT)
From :-Tazeen
Subject :-RE: HW2 Question 4E continued
Comments:- Craig's right.
Date Stamp :- Monday, September 08, 2003 at 14:35:03 (CDT)
From :-Craig Washburn
Subject :-HW2 Question 4E continued
Comments:- It says 'At most one pair of 11 and at most one pair of 00' or something like that. So you could have no occurances, or one of 11 but not 00 and vice versa...right?
Date Stamp :- Monday, September 08, 2003 at 02:48:35 (CDT)
From :-Omer
Subject :-hw2--Q5
Comments:- Does anyone know the definition of 'Mix'?
Date Stamp :- Monday, September 08, 2003 at 02:47:09 (CDT)
From :-Omer
Subject :-HW2--Q4e
Comments:- I think we need to have both 00 and 11 as it says 'and' in the question.
Date Stamp :- Sunday, September 07, 2003 at 21:10:31 (CDT)
From :-Craig Washburn
Subject :-HW2 Question 4E
Comments:- Is it possible to have a string that does not contain '00' or '11'? What about just an occurance of '00' but not 11? Or just '11' and not 00?
Date Stamp :- Thursday, September 04, 2003 at 10:58:03 (CDT)
From :-Tazeen
Subject :-RE: HW1/ Q6
Comments:- It's preferable if you use the rules that are in Dr. Rich's notes (in the background material after the homeworks) or use the ones in Luay's handout. I'm talking about commutativity, distributivity, demorgan's etc. Also remember that a => b can be rewritten as not a or b
and from DeMorgan's you know that not (a ^ b) = not a v not b, you also get not (a v b) = not a and not b.
Date Stamp :- Thursday, September 04, 2003 at 01:12:53 (CDT)
From :-Kevin Chang
Subject :-HW1 / Q6
Comments:- I proved it using the tautological equivalence rules from PHL 313K. It took me 8 steps, but I was rather detailed.
Date Stamp :- Wednesday, September 03, 2003 at 22:23:32 (CDT)
From :-David Rager
Subject :-HW #1/Q6
Comments:- I did (used a truth table)
Date Stamp :- Wednesday, September 03, 2003 at 22:18:36 (CDT)
From :-Ashish Hingorani
Subject :-HW1 / Q6
Comments:- Can we use a truth table to answer this problem?
Date Stamp :- Wednesday, September 03, 2003 at 19:33:58 (CDT)
From :-Tazeen
Subject :-Re: HW #1/ Q3
Comments:- No. If it's asking about positive integers under exponentiation, then it has to be a positive integer with a positive exponent.
Similarly if it was asking about negative numbers under multiplication, it would be negative numbers multiplied with negative numbers.
Date Stamp :- Wednesday, September 03, 2003 at 19:29:30 (CDT)
From :-Ashish Hingorani
Subject :-HW #1/ Q3
Comments:- When it says the positive integers under exponentiation, can u have a positive number and a negative exponent?
Date Stamp :- Wednesday, September 03, 2003 at 17:39:34 (CDT)
From :-Tazeen
Subject :-Re: HW #1/ Q3
Comments:- So for example if the question was, is the set of postive numbers closed under subtraction?
The answer would be No, because if you subtract a postive number from a positive number, it is possible to get something that's not a positive number, such as 3 - 5 = -2.
The respective closure is the minimal set that covers everything in the original set (positive numbers) and also has everything that results from applying the operation... in this case the set of integers. The set of positive numbers plus (or union) the set of integers, is the set of integers.
So the closure is the set of integers.
Date Stamp :- Wednesday, September 03, 2003 at 17:34:33 (CDT)
From :-Tazeen
Subject :-Re: HW1 Q5
Comments:- You have to draw it all out, it's going to have 20 nodes and
lots of connections.
Date Stamp :- Wednesday, September 03, 2003 at 13:17:47 (CDT)
From :-David Rager
Subject :-HW #1/ Q3
Comments:- Question: "If not, what are their respective closures?"
What does it mean by respective? There's more than one operation that the set could be closed under, right? So, we're just naming one example, then?
Date Stamp :- Wednesday, September 03, 2003 at 13:16:17 (CDT)
From :-David Rager
Subject :-RE: HW #1/Q5
Comments:- Yeah, seems like a pain to draw out all those points. In the end, I took my pencil and ruler to the paper and did it.
Date Stamp :- Tuesday, September 02, 2003 at 23:17:32 (CDT)
From :-Omer
Subject :-HW1/ Q#5
Comments:- I was wondering if we have to map all the pairs for reflexive transitive closure of R or just showing couple of them on graph is enough? Any suggestions??
Thanks....
Date Stamp :- Wednesday, August 27, 2003 at 16:57:54 (CDT)
From :-Tazeen
Subject :-Welcome
Comments:- Hello and welcome to the CS341 discussion forum. This forum has been designed for the students in 341, that's you, to communicate with each other. If someone asks a question and you know the answer, do post it... except, ofcourse, don't post solutions to the homeworks or pieces of code for the projects before they're due.
I will also be checking the forum regularly and will respond fairly quickly to any questions.