Discussion section

[ Home   |   Discussion   |   Post ]


Date Stamp :- Friday, August 22, 2003 at 14:34:45 (CDT)
From :-Neetibahl@hotmail.com
Subject :-Theory of computation
Comments:- Construct a DFA accepting the following language over alphabet {0,1}:- (a) L is the set of all strings such that every substring of length 4 contains at least three 1's.


Date Stamp :- Sunday, May 04, 2003 at 13:19:19 (CDT)
From :-Tazeen
Subject :-Re:HW12 #3
Comments:- Prove both, RE and not recursive.

Date Stamp :- Saturday, May 03, 2003 at 20:55:46 (CDT)
From :-Chris
Subject :-HW12 #3
Comments:- Quick question on #3 on the homework -- If the language is recursively enumerable, do we need to prove that it's not recursive and that it's RE (with a turing machine, for example)? Or can we just prove it's not recursive?

Date Stamp :- Wednesday, April 23, 2003 at 13:56:44 (CDT)
From :-
Subject :-HW11
Comments:- Where did some of you guys find sample probs or help for 2-4? Thanks.

Date Stamp :- Wednesday, April 23, 2003 at 13:48:19 (CDT)
From :-Tazeen
Subject :-Re: HW 11 2-4
Comments:- I don't have Dr. Rich's notes with me, but you could try looking at the practice homework solutions at the back.

Date Stamp :- Wednesday, April 23, 2003 at 13:21:46 (CDT)
From :-
Subject :-HW 11 2-4
Comments:- Are there any example problems for HW 11 2-4 in the notes or book to guide us?

Date Stamp :- Wednesday, April 23, 2003 at 13:01:24 (CDT)
From :-Tazeen
Subject :-Homework 11 1a, c
Comments:- This are very vague hints, hope they can be of some help!
For 1 a, first write a grammar the generates wTw^R# .. where T and # are just placeholders, then you have to move T along, copying what you've seen, and moving it over the #.
For 1c, first generate A*b*# for every A you see, keep an a, copy it to another symbol like 1, move the 1 along, when it sees a b, it should have a C, move the C's over the #

Date Stamp :- Wednesday, April 23, 2003 at 12:43:35 (CDT)
From :-Albert
Subject :-Homework 11
Comments:- Me too...Im having trouble with 1a and 1c. please help

Date Stamp :- Tuesday, April 22, 2003 at 21:32:04 (CDT)
From :-
Subject :-HW11
Comments:- ANyone have any hints for 1 a and c. I am having trouble with them.

Date Stamp :- Monday, April 21, 2003 at 11:44:13 (CDT)
From :-Tazeen
Subject :-Project 2 turnin
Comments:- Please turn in Project 2 in the CS homework dropbox in Taylor. Please do not turn it in in Dr. Rich's office, they will not all fit under her door.
If you already put your project under her office door, that's fine.

Date Stamp :- Monday, April 21, 2003 at 11:41:56 (CDT)
From :-Tazeen
Subject :-Re:number 11
Comments:- Did you remember to use %union... to redefine yylval to have a val and a name, and assign to the name when reading the identifier and assign to val when reading a number? then use the name of the id, and use the val of the expr as arguments when calling setsymtab?

Date Stamp :- Monday, April 21, 2003 at 11:37:03 (CDT)
From :-Tazeen
Subject :-Re: project2 part 2, question 14, #4
Comments:- You can use the automatic facility for ques 13 and 14

Date Stamp :- Monday, April 21, 2003 at 11:33:56 (CDT)
From :-Tazeen
Subject :-RE: number 11
Comments:- Did you remember to add %token EQ in expr.y?

Date Stamp :- Monday, April 21, 2003 at 04:16:46 (CDT)
From :-
Subject :-Part II #13
Comments:- Anyone figure out how to skip statements if the booleans are false? Thanks for any help.

Date Stamp :- Monday, April 21, 2003 at 02:31:58 (CDT)
From :-Daniel McPherson
Subject :-project2 part 2, question 14, #4
Comments:- tazeen.... do we have to hand trace this, or can we use the automatic trace facility? (i didn't know which question in part II you were referring to earlier)

Date Stamp :- Sunday, April 20, 2003 at 23:48:53 (CDT)
From :-
Subject :-number 11
Comments:- so im having problems with the assignment, currently i have a new line in expr.l := {return(EQ);} and then in yacc, i added a Line, which whenever you see id EQ expr, it should call the setsymtab procedure, and id is set to goto IDENT. whenever i run the program, im getting a segmentation fault. ive tried typcasting the variables, but for now im confused on what to try next.

Date Stamp :- Sunday, April 20, 2003 at 20:08:33 (CDT)
From :-Tazeen
Subject :-Re:Proj2, Part II, #13: test input
Comments:- Yes you need to be able to read in multiple lines of input.

Date Stamp :- Sunday, April 20, 2003 at 19:57:06 (CDT)
From :-linh
Subject :-Re: Looping for input
Comments:- hint: look for something in the functions at the bottom of your expr.y

Date Stamp :- Sunday, April 20, 2003 at 19:38:24 (CDT)
From :-ph
Subject :-Proj2, Part II, #13: test input.
Comments:- The test case given for #13 (if a=3 then if b=4 then 5 else 6+8) -- are we supposed to set this up so as to be able to accept multiple assignment statements and then evaluate this input? Given as it is, a and b are not in the symbol table. Is this the way its supposed to be?

Date Stamp :- Sunday, April 20, 2003 at 19:11:37 (CDT)
From :-phil
Subject :-Looping for input
Comments:- Could someone help me with how to ask for another set of input. I added to the Line->Expr the yyclearin, but when I enter an expression I get back the answer then a blank line. If I enter another expression I get a syntax error, and then I can enter a new statement. Any help would be great. Thanks

Date Stamp :- Sunday, April 20, 2003 at 15:20:36 (CDT)
From :-Tazeen
Subject :-traces
Comments:- In Part II of the project, you don't have to do the trace by hand, you can use the automatic trace facility.

Date Stamp :- Saturday, April 19, 2003 at 21:34:56 (CDT)
From :-Tazeen
Subject :-Re: if then
Comments:- if (false) then ..
In this case, if you want to assign $$=0, that's fine.
If you decide to do something else that makes sense, that's fine too.
Just don't have your program give syntax errors or crash.

Date Stamp :- Saturday, April 19, 2003 at 16:23:23 (CDT)
From :-Oliver
Subject :-Re: if then
Comments:- erhm... I meant... what are we supposed to do FOR the if BE then S... blablabla

Date Stamp :- Saturday, April 19, 2003 at 16:22:18 (CDT)
From :-Oliver
Subject :-if then
Comments:- I'm having the same problem as Chris... what are we supposed to do if the if BE then S, when the BE is false? Can we just set $$ = 0?

Date Stamp :- Saturday, April 19, 2003 at 03:01:32 (CDT)
From :-Tazeen
Subject :-conflicts
Comments:- In Part II of the project, if you have any conflicts, don't worry about trying to remove them. You should just be able to say if they exist and why you think they do.

Date Stamp :- Saturday, April 19, 2003 at 02:55:18 (CDT)
From :-Tazeen
Subject :-Re:symtab, assign statements
Comments:- For the assignment statement, you need to record the variable names and their values. In order to do that, you've been provided the symtab code.
The symbol table is just a simple array of variable names and values.
You have to use setsymtab(name, val) to save the name, value in the array, and use getsymtab(name) to get the value for the variable name.

Date Stamp :- Saturday, April 19, 2003 at 02:51:56 (CDT)
From :-Tazeen
Subject :-Re:if/then statements
Comments:- Hi Chris, I hadn't really read your question the last time. Sorry, it's late. :-)
You've used the if-statement syntax correctly. Now you just have to debug it.

Date Stamp :- Saturday, April 19, 2003 at 02:29:52 (CDT)
From :-Tazeen
Subject :-Re:if/then statements
Comments:- Hi Chris, the code you write in between { } after the grammar rule is C code, just use a C if-statement, {if ( ) { ...} else { ... } }

Date Stamp :- Saturday, April 19, 2003 at 02:28:02 (CDT)
From :-Tazeen
Subject :-Re:Project 2, Part II
Comments:- Hi Devon, Scroll down, you'll find the answer in earlier posts.

Date Stamp :- Friday, April 18, 2003 at 22:04:32 (CDT)
From :-Chris
Subject :-if/then statements
Comments:- I'm not sure how to write the code for the if/then statement. I tried the rule Statement : IF Boolean THEN Statement {if($2) $$ = $4;}, but regardless of what boolean i put in I always get the statement back and an error. How can I get the parser to totally skip the statement if the boolean is false?

Date Stamp :- Friday, April 18, 2003 at 21:34:36 (CDT)
From :-Devon
Subject :-Project 2, Part II
Comments:- I'm having trouble getting the redefinition of yylval to work. After replacing $$ and the like to $$.val, I get errors of the form "$$ of 'expr' has no declared type". If anyone has gotten these errors too or knows how to fix them, hook it up. Thanks

Date Stamp :- Friday, April 18, 2003 at 19:49:36 (CDT)
From :-Steve
Subject :-symtab, assign
Comments:- When reducing s -> id := expr, you will need to set the variable name to a value. However, when reducing id -> name, you will need to get the variable's value.

Date Stamp :- Friday, April 18, 2003 at 19:16:03 (CDT)
From :-joe salinas
Subject :-symtab, assign statements
Comments:- I'm a little stuck on Proj 2. Why are we using the symtab code? When do we need to maintain the symbol table for our project? Also, any suggestions on how to save our results from our assignment statements? Thanks!

Date Stamp :- Friday, April 18, 2003 at 11:49:00 (CDT)
From :-Rafael
Subject :-Re: that
Comments:- Thanks much

Date Stamp :- Thursday, April 17, 2003 at 22:49:38 (CDT)
From :-Chris
Subject :-Project2, Problem 9
Comments:- To get invert and square added, you need your lex rules to return a different token than NUMBER. I think the easiest way to do it it to have "invert" return a token INVERT and "square" a token SQUARE. Then, define in your yacc file %token INVERT and %token SQUARE. You can then refer to them in your rules with INVERT and SQUARE.

Date Stamp :- Thursday, April 17, 2003 at 21:49:06 (CDT)
From :-Rafael
Subject :-Project2, Problem 9
Comments:- I'm having a hard time understanding exactly how you add invert and square to your lex rules.. I tried making it its own rule: "invert" {return(NUMBER);} But apparently that's very wrong, because then it gives me a syntax error when I try invert(whatever) as input. I did some variations on that line; with and without quotes, etc, but nothing so far. I'm pretty sure my grammar's right, I just don't know how they should be added to expr.l

Date Stamp :- Thursday, April 17, 2003 at 18:14:15 (CDT)
From :-Chris
Subject :-Project 2, accepting more than one line of input
Comments:- I'm getting shift/reduce conflicts on my grammar and I'm not sure why. Right now what I have is: Line -> Statement Line Line -> QUIT Statement -> IDENT := expr Statement -> expr Statement -> error I know for sure the problem is in these rules, but I'm not sure where the conflict is. Yacc seems to see "IDENT := expr", expr, and error as the same thing.

Date Stamp :- Thursday, April 17, 2003 at 01:25:32 (CDT)
From :-Tazeen
Subject :-$<val>1 vs. $<name>1
Comments:- The type of yylval has been defined as a union of val and name. $1, $$ are yylval's. Since it's a union, at any time, yylval will either be a val or a name, but not both. You'll want it to be a name when you're using it for an identifier, but be a val when you're using it as a number.
When you're using $1 in your grammar rules, remember if what you're talking about is an identifier or a number.


Date Stamp :- Thursday, April 17, 2003 at 01:17:25 (CDT)
From :-Tazeen
Subject :-New if-statement grammar Project 2 #13
Comments:- These are the new grammar rules for the if-statement. Please implement these and not the ones given to you originally.

S -> if BE then S

S -> if BE then S else S

S->expr | BE where expr is the expression defined in Part I


Date Stamp :- Thursday, April 17, 2003 at 01:12:33 (CDT)
From :-Tazeen
Subject :-Re: Homework 10: 1, 2
Comments:- Just R means move the head on the input tape 1 step to the right.
R subscript a means keep moving the input tape head to the right until you see an a.
Remember that R subscript a, will always move the head at least one step to the right.
So if you begin with the tape head on an a, it will take one step right, check if it's an a, if it is it stops, if it isn't it moves right and checks again, and so on.
If a is a subscript after R, it means move right till you see an a. If it is on the same line after R, like Ra, it means move right one step, then write a on the tape.
Be aware that when you use R subscript a, it's not going to stop moving right until it sees an a. If your string doesn't have any a's it will read and skip the rest of the string, then it will read and skip the blanks.. and since those are infinite, it will never stop.
If it says R subscript a, b. Then it will move right until it sees an a or a b. It will stop on whichever of the two it sees first.
Similarly for L.

Date Stamp :- Wednesday, April 16, 2003 at 19:19:18 (CDT)
From :-Daniel McPherson
Subject :-Homework 10: 1, 2
Comments:- I had to miss class on the day she explained R[theta] and other simple routines(?).... can someone briefly describe what these are and what they do?

Date Stamp :- Wednesday, April 16, 2003 at 16:09:00 (CDT)
From :-
Subject :-
Comments:- What's the difference between $1 and $1? Or they synonomous, or do they have different effects when used in the rules?

Date Stamp :- Wednesday, April 16, 2003 at 15:22:27 (CDT)
From :-Tazeen
Subject :-RE: Proj2 again because of HTML
Comments:- You have to use the $<name>1 or $<val>1 kind of syntax if you're using Linux. If you're using Sun machines, use $1.name or $1.val.

Date Stamp :- Wednesday, April 16, 2003 at 15:18:39 (CDT)
From :-Tazeen
Subject :-Re: Proj2
Comments:- Hi Steve, You have to use the $1 or $1 kind of syntax if you're using Linux. If you're using Sun machines, use $1.name or $1.val.
Hope this helps.

Date Stamp :- Wednesday, April 16, 2003 at 14:52:18 (CDT)
From :-Tazeen
Subject :-13
Comments:- The grammar doesn't seem to allow nested if-statements, I've emailed Dr. Rich to ask what she wants to do about it. When she lets me know, I'll let you know.

Date Stamp :- Wednesday, April 16, 2003 at 14:07:34 (CDT)
From :-Daniel
Subject :-#13
Comments:- I also do not see how we can have nested if statements, as they are not allowed by the grammer!

Date Stamp :- Tuesday, April 15, 2003 at 23:25:21 (CDT)
From :-James
Subject :-Project 2 - #13
Comments:- On #13, the specification says: S -> if BE then S1 ; S -> if BE then S1 else S1; S1 -> expr | BE. My question is how can we have "if BE then if BE then ... else ..." ? The if/then/else statements are not constructed by S1. The grammar does not allow nested if statements.

Date Stamp :- Tuesday, April 15, 2003 at 18:41:15 (CDT)
From :-Steve
Subject :-Proj2
Comments:- After adding all the $ < name > 1, $ < val > 1, etc, anyone have the problem that their program isn't working anymore? Such as: a.out ? 1+3 (produces nothing) Also, is it $ < name > 1 or $ < name > $1? One way it doesn't work, and the other way I get an error saying "no union name1".

Date Stamp :- Tuesday, April 15, 2003 at 13:20:30 (CDT)
From :-James
Subject :-RE: project2 part 2, question 11
Comments:- It actually doesn't match them to NUMBER. What's happening is that there are no rules to match '.' or ';' etc. So lex just outputs them back.

Date Stamp :- Tuesday, April 15, 2003 at 12:12:18 (CDT)
From :-Tazeen
Subject :-Typo
Comments:- In the post about the changes you have to make to do the identifiers, Point 4 has the rule for identifier as:
[A-Za-z][A-za-z0-9_]* {strncpy(yylval.name, yytext, 20); return (IDENT);
It should be: [A-Za-z][A-Z a-z0-9_]* {strncpy(yylval.name, yytext, 20); return (IDENT); Sorry about that!

Date Stamp :- Tuesday, April 15, 2003 at 12:07:14 (CDT)
From :-Tazeen
Subject :-Re: project2 part 2, question 11
Comments:- Don't worry about it.

Date Stamp :- Tuesday, April 15, 2003 at 00:24:43 (CDT)
From :-Daniel McPherson
Subject :-project2 part 2, question 11
Comments:- why does lex match more than it should for a NUMBER? for example, in my expr.l file, i have this line: [0-9]+ {yylval.val = atoi(yytext); return(NUMBER);} but when i compile everything and run the program, it will process this: ? ...5 ...5 ? ...6+5 ...11 ? ;';4 ;';4 ? ..4... .....4 ? ;;;;4;;; ;;;;;;;4 ? ;;;;4;..;;+ .5..;; ;;;;;..;; ...;;9 i tried this with other non alphanumeric characters, and it seems to match most, except forward slash. do we need to fix this, or not worry about it?

Date Stamp :- Monday, April 14, 2003 at 18:49:55 (CDT)
From :-
Subject :-
Comments:- $ < name > $1 or $ < name > 1

Date Stamp :- Monday, April 14, 2003 at 18:48:17 (CDT)
From :-Steve
Subject :-Part 2
Comments:- Is it supposed to be $1 or $$1 ? Because I get new errors with the second option, and with the first option the program works incorrectly.

Date Stamp :- Monday, April 14, 2003 at 14:25:18 (CDT)
From :-Tazeen
Subject :-identifiers in lex
Comments:- Make sure you put the identifier rule in lex after the rules for square, quit, invert etc. Otherwise lex will treat square as an identifier.

Date Stamp :- Monday, April 14, 2003 at 12:42:04 (CDT)
From :-Mike
Subject :-Proj2 - part 2 (AGAIN BECAUSE OF HTML)
Comments:- Wherever you have $$ make it $<val>$, wherever you have $1 make it $<val>1 or $<name>$1

Date Stamp :- Monday, April 14, 2003 at 12:39:50 (CDT)
From :-Mike
Subject :-Proj2 - part 2
Comments:- I am doing the project 2 using yacc on the linux computers here at the university.

I had trouble using the syntax provided in Tazeen's help for part II of the project. I followed all the instructions, but using $1.val or $1.name in place of $1 resulted in an error:

$1 of 'expr' has no declared type

I was able to fix the problem by using this syntax which I found in the yacc reference guide:

Wherever you have $$ make it $$, wherever you have $1 make it $1 or $$1

Date Stamp :- Monday, April 14, 2003 at 12:10:34 (CDT)
From :-Tazeen
Subject :-Recompile
Comments:- If you're making changes to your expr.l and expr.y and you do lex expr.l and yacc expr.y but it doesn't seem to make any difference.. make sure you've recompiled your files and aren't using the old a.out.
It's unbelievable how many times that happens.

Date Stamp :- Monday, April 14, 2003 at 12:08:47 (CDT)
From :-Tazeen
Subject :--
Comments:- - is a special character for lex, it can be used to define ranges. If you want to use the - character itself make sure it's the first or last character.
[A-Z] means all the characters from A to Z [-AZ] means just the three characters -, A and Z.
So when you're adding * and /, make sure you're careful about where - is.

Date Stamp :- Sunday, April 13, 2003 at 21:59:49 (CDT)
From :-Tazeen
Subject :-Re: project2 part 1, question 9
Comments:- you'll get the points anyway :-) I don't expect you to invent conflicts if there are none.

Date Stamp :- Sunday, April 13, 2003 at 21:25:58 (CDT)
From :-Daniel McPherson
Subject :-project2 part 1, question 9
Comments:- "..if you use the tracing facility, annotate it so it's clear that you know what it is doing." what if we have no conflicts? what annotation will we be graded on?

Date Stamp :- Sunday, April 13, 2003 at 21:25:27 (CDT)
From :-Tazeen
Subject :-Re: project2 part 1, problem 8
Comments:- As an example, you should be able to evaluate -5+-5 to -10

Date Stamp :- Sunday, April 13, 2003 at 21:24:01 (CDT)
From :-Tazeen
Subject :-Re: project2 part 1, problem 8
Comments:- anywhere

Date Stamp :- Sunday, April 13, 2003 at 03:36:21 (CDT)
From :-Daniel McPherson
Subject :-project2 part 1, problem 8
Comments:- can the unary operator be anywhere in the expression, or just at the very beginning?

Date Stamp :- Saturday, April 12, 2003 at 20:59:18 (CDT)
From :-Tazeen
Subject :-Re: project2 part 1, question 4 continued
Comments:- State 3 is on top of the stack. Look at state 3, it has a rule expr: NUMBER_ (2). The underline after the number means you've already read the number. You can reduce NUMBER to expr by the grammar rule 2, doesn't have anything to do with the states, and should not be put on the stack.
Pop off the state 3, and the NUMBER from the stack. Push on expr. Now look at the top most (or rightmost) state on the stack, it is 0. Look at state 0 and see where it goes on an expr. It says expr goto 2. Push state 2 on the stack. Now you have:
Step Stack Input Action
1 $(0) 4$ shift
2 $(0)4(3) $ reduce
3 $(0)expr(2) $
The topmost state is 2. Look at state 2, you can reduce expr to Line. popoff state 2 and expr, replace it with Line. The topmost state is 0, look at state 0, it goes to state 1 on Line. Push 1 on the stack.
Step Stack Input Action
1 $(0) 4$ shift
2 $(0)4(3) $ reduce
3 $(0)expr(2) $ reduce
4 $(0)Line(1) $

Look at state 1, it has the rule $accept: Line_$end.
The _ in the middle means you've already read line, and $ is the next thing in the input. So you can accept
Step Stack Input Action
1 $(0) 4$ shift
2 $(0)4(3) $ reduce
3 $(0)expr(2) $ reduce
4 $(0)Line(1) $ accept


Date Stamp :- Saturday, April 12, 2003 at 20:58:26 (CDT)
From :-Tazeen
Subject :-Re: project2 part 1, question 4
Comments:- Read the yacc manual part 4: How the Parser Works.
Here's a small example, the numbers of your states may differ. If your input is 4, you'd have
Step Stack Input Action
1 $(0) 4$
Look at state 0, it has a rule NUMBER shift 3
This is what you have so far:
Step Stack Input Action
1 $(0) 4$ shift
2 $(0)4(3) $



Date Stamp :- Saturday, April 12, 2003 at 19:48:42 (CDT)
From :-Daniel McPherson
Subject :-project2 part 1, question 4
Comments:- i'm having trouble tracing through the program by hand. any general hints to give? also... what do you do when you are in a state that has no "go to state xy" or "shift" statements in them? do you return from the state that sent you there originally?

Date Stamp :- Friday, April 11, 2003 at 15:44:46 (CDT)
From :-Tazeen
Subject :-symtab files
Comments:- symtab.h
symtab.c


Date Stamp :- Friday, April 11, 2003 at 14:12:08 (CDT)
From :-Tazeen
Subject :-Project 2 Part II continued
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.

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 :- Friday, April 11, 2003 at 14:11:29 (CDT)
From :-Tazeen
Subject :-Project 2 Part II
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 :- Wednesday, April 09, 2003 at 18:05:17 (CDT)
From :-Tazeen
Subject :-Project 2
Comments:- If you need to save output to the console to a file. At the prompt, type script filename. Example vampire>script output.txt.
Everything that you type or that gets printed on the screen will be saved in filename until you type exit. Then you can edit filename in any editor.

Date Stamp :- Wednesday, April 09, 2003 at 18:01:22 (CDT)
From :-Tazeen
Subject :-Project 2
Comments:- If you tried to use Dr. Rich's expr.y and expr.l without changing them and got strange errors, it's because the dos end-of-line is different from the unix end-of-line. You can do any one of the following things:
1. retype the files
2. use the dos2unix command. Ex. dos2unix expr.l
3. open the file in a unix editor such as pico or emacs. do anything that would require it to save the file again when you exit, such as hit space or enter, then save and exit.

Date Stamp :- Tuesday, April 08, 2003 at 13:51:21 (CDT)
From :-Tazeen
Subject :-Midterm 2 grade cut offs
Comments:- 110-135 A
100-109 B
70-99 C
50-69 D


Date Stamp :- Tuesday, April 01, 2003 at 12:24:23 (CST)
From :-Tazeen
Subject :-Re: HW9 Q 1d
Comments:- When using closure properties, if you're using a property under which a CFL is closed, you get back a CFL.
However remember that every regular language is a CFL language (although not every CFL is a regular language).
So if you using closure properties to get back a CFL, it doesn't prove that the language is not regular.


Date Stamp :- Tuesday, April 01, 2003 at 00:28:31 (CST)
From :-Oliver
Subject :-3a
Comments:- use closure properties (of regular langs and CFLs)

Date Stamp :- Monday, March 31, 2003 at 22:42:41 (CST)
From :-jason
Subject :-3a
Comments:- I was able to get 3b fine but i can not seem to get anywhere on 3a. I do not know whether it is even true or false. Can someone guide me in the right direction?

Date Stamp :- Monday, March 31, 2003 at 18:46:54 (CST)
From :-Phil
Subject :-Hw 9 Q 1d
Comments:- Can we just show L is context free, then use the closure properties to say L* is context free. Am I using it backwards, thanks

Date Stamp :- Monday, March 31, 2003 at 13:32:26 (CST)
From :-James
Subject :-hw9 4b
Comments:- Ya, it's tricky... I came up with the algorithm, but can't describe it clearly on paper. It can be proven that Alt(L) is closed under CFL.

Date Stamp :- Monday, March 31, 2003 at 13:26:29 (CST)
From :-Jeff Sampson
Subject :-HW #9: 4b.
Comments:- How do you do 4b? I'm getting a headache trying to reason about it.

Date Stamp :- Monday, March 31, 2003 at 01:54:43 (CST)
From :-Tazeen
Subject :-Re: HW9 ques1d
Comments:- L has many strings.
L* doesn't have to concatenate the same string to itself.
In L*, the different pairs of 1's don't have to have the same number of 1's as each other.
Also remember the 0*.. there doesn't have to be a 0 in the middle of two sections of 1's.

Date Stamp :- Monday, March 31, 2003 at 01:45:38 (CST)
From :-Tazeen
Subject :-HW9
Comments:- Homework 9 is due Tuesday 8:30 am. I don't know about the quiz

Date Stamp :- Sunday, March 30, 2003 at 17:24:38 (CST)
From :-Rezwan
Subject :-HW 9 and Quiz
Comments:- Is the HW and Quiz both due by 8:30 am tomorrow?

Date Stamp :- Saturday, March 29, 2003 at 23:29:11 (CST)
From :-James
Subject :-Hw 9 Q 1d
Comments:- Hmm... it seems to me that L* is not tricky at all... maybe I'm not seeing it... but it looks like a very simple CF language.

Date Stamp :- Thursday, March 27, 2003 at 21:54:09 (CST)
From :-Chris
Subject :-HW8, #1d
Comments:- I just wanted to check that I understand L* correctly since it is supposed to be tricky and it doesn't seem like it. Since L is 0* 1^n 0* 1^n 0*, L* should just be 0* 1^n 0* 1^n 0* 1^n 0* 1^n 0*... where 1^n appears an even number of times. Is that right?

Date Stamp :- Wednesday, March 26, 2003 at 22:22:20 (CST)
From :-Tazeen
Subject :-HW 8 question 2
Comments:- Sorry, I read your post too late. The answers to homework 8 are posted.

Date Stamp :- Wednesday, March 26, 2003 at 14:10:07 (CST)
From :-Jeremy
Subject :-HW 8 Question 2
Comments:- I think I understand the Language, accepting all strings that have the form: b a^m1 b a^m2 ... where m1, m2, etc. are variables of positive integers. So the minimum string would be either bba or bab, given that m1 and m2 can be either 0 or 1. I believe that you cannot keep track of the length of strings of a's between each b with only 1 stack. So, how would you make this PDA? Am I reading the question wrong? please help! Thanks

Date Stamp :- Wednesday, March 26, 2003 at 14:10:07 (CST)
From :-Jeremy
Subject :-HW 8 Question 2
Comments:- I think I understand the Language, accepting all strings that have the form: b a^m1 b a^m2 ... where m1, m2, etc. are variables of positive integers. So the minimum string would be either bba or bab, given that m1 and m2 can be either 0 or 1. I believe that you cannot keep track of the length of strings of a's between each b with only 1 stack. So, how would you make this PDA? Am I reading the question wrong? please help! Thanks

Date Stamp :- Wednesday, March 26, 2003 at 14:10:05 (CST)
From :-Jeremy
Subject :-HW 8 Question 2
Comments:- I think I understand the Language, accepting all strings that have the form: b a^m1 b a^m2 ... where m1, m2, etc. are variables of positive integers. So the minimum string would be either bba or bab, given that m1 and m2 can be either 0 or 1. I believe that you cannot keep track of the length of strings of a's between each b with only 1 stack. So, how would you make this PDA? Am I reading the question wrong? please help! Thanks

Date Stamp :- Wednesday, March 26, 2003 at 14:09:07 (CST)
From :-Jeremy
Subject :-HW 8 Question 2
Comments:- I think I understand the Language, accepting all strings that have the form: b a^m1 b a^m2 ... where m1, m2, etc. are variables of positive integers. So the minimum string would be either bba or bab, given that m1 and m2 can be either 0 or 1. I believe that you cannot keep track of the length of strings of a's between each b with only 1 stack. So, how would you make this PDA? Am I reading the question wrong? please help! Thanks

Date Stamp :- Tuesday, March 25, 2003 at 14:35:19 (CST)
From :-luay
Subject :-2nd midterm review session (and handout)
Comments:- As you know, the review session for the second midterm is going to be held on Sunday, March 30, at 6:00 pm, in TAY 2.106. I have prepared a set of practice problems that we can work on in the review session. The handout can be downloaded at: http://www.cs.utexas.edu/users/nakhleh/2nd_midterm_review_sp03.ps (PS) http://www.cs.utexas.edu/users/nakhleh/2nd_midterm_review_sp03.pdf (PDF) Please, make sure you bring a copy of the handout to the review session, since I'm not going to make copies. It is very important that you work on these problems before you come to the review session. Also, remember that this review session is dedicated to YOUR questions and not MINE! So, make sure that you have a list of any questions you may have about the material and that are not covered on the handout. One other point: I am not going to discuss conversion algorithms in the review session (CFG's <--> PDA's). However, I WILL cover Chomsky Normal Form (the actual algorithm on an example, and applications). If you have any problems with a topic that is not covered on the handout, feel free to email me before the session so that I prepare some examples. Luay

Date Stamp :- Monday, March 24, 2003 at 13:59:08 (CST)
From :-Tazeen
Subject :-Re: HW 8, #1 d and e
Comments:- Hi Chris,
You're right, the only difference in the two languages is that in one the order matters and in the other it doesn't.
If you want, you may be able to use closure properties and the fact that the first language is not context free to prove that the second language is not context free.


Date Stamp :- Sunday, March 23, 2003 at 19:50:41 (CST)
From :-Chris
Subject :-HW 8, #1 d and e
Comments:- Is it just me or are these two problems basically the same? Sure e) lets you have the 0's and 1's in any order, but you could still set up the pumping theorem just like d) to prove that it's not context free... right? It seems too strange to me that the exact same solution could be used twice, so I'm wondering if I'm missing something here.

Date Stamp :- Wednesday, March 19, 2003 at 17:43:27 (CST)
From :-Tazeen
Subject :-Re: HW#7 #2
Comments:- Try your algorithm on a madeup L to check if it works.

Date Stamp :- Wednesday, March 19, 2003 at 17:42:06 (CST)
From :-Tazeen
Subject :-Re: HW#7 #2
Comments:- For context free languages, when you have to come up with decision procedures, remember CNF.
If you have a Context free language, it can be defined in CNF. That means the grammar has rules only of two kinds: A -> BC, D -> d
Init(L) is the language containing the prefixes of the strings in L.
Think of how you would convert (or maybe add to) the grammar rules for L to get grammar rules for init(L).
You could write for every rule of the form A -> BC in the CNF grammar for L, I will add the rule A' -> (you figure this out) to the grammar for init(L), where A' is the prefix of A. Similary for every rule of the form D -> d, I will add the rule D' -> (whatever you think right) to the grammar for init(L).
Since the resulting grammar for init(L) is a context free grammar, therefore context free languages are closed under the operation init(L)

Date Stamp :- Wednesday, March 19, 2003 at 17:32:30 (CST)
From :-Tazeen
Subject :-Re: Homework 7: #1.d
Comments:- Take advantage of non-determinism. Assume that given multiple options (for popping off symbols from the stack), the PDA will always make the right choice in order to accept the string.
Just make sure there's at least one way to accept a string that should be in the language, and no way to accept one that isn't. Hope that helps

Date Stamp :- Wednesday, March 19, 2003 at 17:28:05 (CST)
From :-Daniel McPherson
Subject :-HW#7 #2
Comments:- any ideas on this one?

Date Stamp :- Wednesday, March 19, 2003 at 17:27:47 (CST)
From :-Danie
Subject :-HW#7 #2
Comments:-

Date Stamp :- Tuesday, March 18, 2003 at 23:24:23 (CST)
From :-Daniel McPherson
Subject :-Homework 7: #1.d
Comments:- anyone have any clues on this one?

Date Stamp :- Tuesday, March 18, 2003 at 11:08:11 (CST)
From :-Tazeen
Subject :-CFG -> PDA
Comments:- I've posted the algorithm for CFG -> PDA in the Notes section.
For PDA -> CFG, you just need to know that an algorithm exists for it, but you're not required to know how to use it.

Date Stamp :- Monday, March 17, 2003 at 11:35:48 (CST)
From :-Tazeen
Subject :-Re: context free <-> pda
Comments:- Sorry for taking so long to reply. I was enjoying spring break :-)
The main thing for you to know is that given a context free grammar, it is possible to derive an equivalent pda and vice versa (may help in writing decision procedures).
It is pretty straightforward going from a CFG to a PDA, the other direction is more complicated. I'll ask Dr. Rich if you really have to know how to convert a PDA to a CFG, if she says yes, then I'll post something by next Monday for CFG <-> PDA, otherwise just for CFG -> PDA, sorry for taking so long, I'll try to post it sooner but this week is a little crazy for me.


Date Stamp :- Thursday, March 06, 2003 at 17:48:50 (CST)
From :-ph.
Subject :-context-free <-> PDA
Comments:- The guide you posted for converting NDFSM -> FSM was extremely helpful. Will you be posting a guide for converting context-free grammar -> PDA and PDA -> context-free grammar?

Date Stamp :- Thursday, March 06, 2003 at 09:58:31 (CST)
From :-Tazeen
Subject :-Re: HW6 #4
Comments:- Note: the empty set is also regular. A regular set doesn't have to have an element.

Date Stamp :- Thursday, March 06, 2003 at 09:55:56 (CST)
From :-Tazeen
Subject :-Re: HW6 #4
Comments:- Any set containing just a single element is regular. The union, kleene star, and concatenation of regular sets results in a regular set.
Examples: {0}
{}
{epsilon}
{0} U {1} = {0, 1}, so {0, 1} is a regular set
{0, 1}*
{0, 1}* {0, 1} = {0, 1}+, so {0, 1}+ is a regular set

Date Stamp :- Wednesday, March 05, 2003 at 22:04:17 (CST)
From :-
Subject :-HW6 #4
Comments:- Does regular set mean a set or is this some special type of set???

Date Stamp :- Tuesday, March 04, 2003 at 20:09:39 (CST)
From :-
Subject :-Make thousands quick and easy! Not a scam! Works great!
Comments:- Become rich...Turn $6 to $6,000 in days...Read to learn how... AMAZING PLAN TO BECOME RICH IN DAYS HOW TO BECOME RICH HOW TO TURN SIX DOLLARS INTO MILLIONS OF DOLLARS: READING THIS COULD CHANGE YOUR LIFE! IT TRULY WORKS! I found this on a bulletin board and decided to try it. A little while back, I was browsing through newsgroups, just like you are now, and came across an article similar to this that said you could make hundreds of thousands of dollars within weeks (which would soon turn into millions) with only an initial investment of $6.00! So I thought, "Yeah right, this must be a scam", but like most of us, I was curious, so I kept reading. Anyway, it said that you send $1.00 to each of the 6 names and address stated in the article. You then place your own name and address in the bottom of the list at #6, and post the article in at least 250 newsgroups. (There are thousands) No catch, that was it. So after thinking it over, and talking to a few people first, I thought about trying it. I figured: "what have I got to lose except 6 stamps and $6.00, right?" Then I invested the measly $6.00 (I use the word "measly" because $6 really is measly compared to the money I have made through the initial investment). Well GUESS WHAT!?... within 7 days, I started getting money in the mail! I was shocked! I figured it would end soon, but the money just kept coming in. In my first week, I made about $25.00. By the end of the second week I had made a total of over $1,000! In the third week I had over $10,000 and it's still growing. This is now my fourth week and I have made a total of just over $42,000 and it's still coming in rapidly. It's certainly worth $6.00, and 6 stamps, I have sp

Date Stamp :- Tuesday, March 04, 2003 at 19:17:27 (CST)
From :-Tazeen
Subject :-Exam grades
Comments:- The grades are not posted online.


Date Stamp :- Monday, March 03, 2003 at 17:28:31 (CST)
From :-Pallav
Subject :-Exam Grades
Comments:- I wanted to know if the exam grades are going to posted online or the newsgroup anytime soon. thanks

Date Stamp :- Thursday, February 27, 2003 at 10:19:31 (CST)
From :-Tazeen
Subject :-Re: Worksheet 2 #6d
Comments:- Since it's a NDFSM, it's fine as it is. There should be at least one way to accept every string that is in the language, and it shouldn't accept any strings that are not in the language.

Date Stamp :- Wednesday, February 26, 2003 at 18:08:25 (CST)
From :-phil
Subject :-Worksheet 2, # 6d
Comments:- Should the initial state have a loop to 1, since seeing one 1 will put the machine in the final state, or should it just have a loop for 0? Thanks

Date Stamp :- Wednesday, February 26, 2003 at 15:00:54 (CST)
From :-Tazeen
Subject :-Re: Regular Grammars
Comments:- There's an algorithm in Dr. Rich's notes for going from a regular grammar to a NDFSM

Date Stamp :- Wednesday, February 26, 2003 at 09:40:12 (CST)
From :-Jeff
Subject :-Midterm
Comments:- Can you take the midterm at any of the three sections on thursday?

Date Stamp :- Wednesday, February 26, 2003 at 04:06:42 (CST)
From :-Steve
Subject :-Regular Grammars
Comments:- Is there an algoritm to go from regular grammars to FSMs, or vice versa? Thanks.

Date Stamp :- Tuesday, February 25, 2003 at 21:59:54 (CST)
From :-Tazeen
Subject :-Re:equivalence classes
Comments:- Oops there's a mistake in the earlier post. The equivalence clases would be
[epsilon]
[ab*] since getting 0 or more b's after the a doesn't make a difference
[everything else]


Date Stamp :- Tuesday, February 25, 2003 at 21:57:51 (CST)
From :-Tazeen
Subject :-Re: equivalence classes
Comments:- You can either try to come up with a minimal fsm for the language. or think of states in terms of how much work has been done to get to strings in the language, so if the language is ab*, eqivalence classes would be
[epsilon] no work done
[a] gotten an a
[ab*] gotten the strings
[everything else] that's the dead state

Date Stamp :- Tuesday, February 25, 2003 at 21:54:08 (CST)
From :-Tazeen
Subject :-Re: Regular Grammars on the test
Comments:- Everything before Context Free Languages that Dr. Rich has taught could be on the exam. so regular grammars may be on it.

Date Stamp :- Monday, February 24, 2003 at 21:08:19 (CST)
From :-
Subject :-Regular Grammars on the test
Comments:- Are regular grammars going to be covered on the test?

Date Stamp :- Monday, February 24, 2003 at 19:45:33 (CST)
From :-Danny McPherson
Subject :-equivalence classes
Comments:- What is the best way to figure out equivalence classes?

Date Stamp :- Monday, February 24, 2003 at 18:49:45 (CST)
From :-Chris
Subject :-Regular Languages Closures
Comments:- Look at Closures on page 38 of the packet (page 2 of Lecture notes 8). It lists Union, Concatenation, Kleene Star, Complementation, and Intersection.

Date Stamp :- Monday, February 24, 2003 at 17:48:56 (CST)
From :-Jason
Subject :-Regular language closures
Comments:- Regular languages are closed under *, intersection, compliment, union (by intersection and compliment). Are there any more, such as concatenation???

Date Stamp :- Sunday, February 23, 2003 at 18:45:20 (CST)
From :-Atri
Subject :-Decision Procedures
Comments:- The basic method for coming up with a decision procedure is to formulate the current decision procedure equivalently in terms of other "known" decision procedure(s) (like checking if a a regular language is empty or if two DFAs are equivalent). The whole trick of course here is to make the equivalent formulation which depends on the current problem in hand. Unfortunately there is no fixed procedure to do this conversion but the following facts maybe useful-- (*) equivalence of regular languages and FSMs (*) uniqueness (upto renaming of states) of a minimized DFA (*) Closure properties of set operations on languages (*) Certain "well-known" regular languages. See the solution for problem #2 in Hw #4 for an example. This is a common "trick" known as reduction.

Date Stamp :- Sunday, February 23, 2003 at 18:17:43 (CST)
From :-Tazeen
Subject :-Re: Homework 5
Comments:- HW5 ques 2. x#y, x and y are going to be made up of 0s and 1s. # is just #. So you'll get strings like 01010#1010011001. The # allows lets you know where x ends and y begins.

Date Stamp :- Sunday, February 23, 2003 at 12:10:51 (CST)
From :-Chris Parsons
Subject :-Homework 5
Comments:- On HW5, #2, what does x#y mean? I'm pretty sure it was defined on a previous homework, but I don't remember what it was.

Date Stamp :- Tuesday, February 18, 2003 at 19:22:12 (CST)
From :-Tazeen
Subject :-Project 1 Missing info
Comments:- If some input is not provided to your program, it should recognize the fact, give as much info to the user as possible and do whatever you want. Just remember to include what you decide to do in the users manual.

Date Stamp :- Tuesday, February 18, 2003 at 16:45:27 (CST)
From :-Mike F.
Subject :-Test Cases - Machine 6 transition relation problem
Comments:- On the test cases, Machine 6 has a transition relation q3, x, q4. But q4 is not in the set of states. Should q4 be added to the set of states? Is q4 a final state?

Date Stamp :- Tuesday, February 18, 2003 at 16:39:16 (CST)
From :-Mike F.
Subject :-Test Cases - Machines 4 and 5 are missing initial, final states
Comments:- On the project 1 test cases page... http://www.cs.utexas.edu/users/ear/cs341/project1tests.txt Machine #4 does not define an initial state. Machine #5 does not define an initial state or final states. What are the initial and final states for these machines supposed to be?

Date Stamp :- Monday, February 17, 2003 at 15:39:43 (CST)
From :-Luay
Subject :-review session handout
Comments:- Dear students, I will be giving the review session for the first exam on Sunday, Feb 23, from 6 to 10, at TAY 2.106. The purpose of the review session is to answer your questions and help you better understand the material, so the first priority will be given to YOUR questions. Nevertheless, I have also prepared a set of problems for you to practice just in case you need more problems to work on. Please try your best to work on these problems before the review session; that will make the session more effective and efficient. Also, make sure you bring a copy of the handout with you (I'm not going to make copies; it's your duty to print out the handout and bring it with you). The handout can be accessed at: http://www.cs.utexas.edu/users/nakhleh/1st_midterm_review_sp03.pdf (PDF) http://www.cs.utexas.edu/users/nakhleh/1st_midterm_review_sp03.ps (PS) VERY IMPORTANT: the handout may contain some "challenging" problems. DO NOT panic if you can't solve them; they do not reflect what's going to be on your exams. Those questions are there for those students who are interested in "more challenging" problems. Feel free to email me with any questions you may have about the handout. Please do not ask me to solve any of these problems for you at this point, since I prefer to do that in the review session (that way more students will be exposed to the solutions). Thank you. Luay (nakhleh@cs.utexas.edu)

Date Stamp :- Friday, February 14, 2003 at 11:53:17 (CST)
From :-Tazeen
Subject :-{a, b}+
Comments:- {a, b}* means strings of length 0 or more containing a's and/or b's.
{a, b}+ means strings of length 1 or more containing a's and/or b's.
It's the same as {a, b}* - {epsilon}.

Date Stamp :- Wednesday, February 12, 2003 at 12:15:43 (CST)
From :-KD
Subject :-{a,b}+
Comments:- In HW 4, what does the + mean in question 1 part e where there exists x in {a,b}+?

Date Stamp :- Monday, February 10, 2003 at 10:26:16 (CST)
From :-Tazeen
Subject :-Project 1
Comments:- Message from Dr. Rich ---- You have a choice in how to handle inputs to your simulator for project 1. You can either: - accept input typed interactively to your program, or - accept a file that contains the input machines You can do it either way, but it's easier if you use a file because then you won't have to retype your test cases every time you run them. It's also okay if you want to make a graphical front end, but that's way more than you need to do. ER

Date Stamp :- Wednesday, February 05, 2003 at 22:51:00 (CST)
From :-Tazeen
Subject :-HW 3 ques 3
Comments:- One way to think about it is, given a FSM for L, how would you construct a FSM for Pref(L). To think about it, try a few example Ls, such { ab, bba}, construct a FSM for it. Then think about what changes you would make to the FSM to get a FSM for the Pref(L), it should accept {epsilon, a, ab, b, bb, bba}. Then try to come up with a general algorithm that works for any L. Write that in english as the answer.

Date Stamp :- Wednesday, February 05, 2003 at 22:17:59 (CST)
From :-James
Subject :-HW3 - Question 3
Comments:- Anyone else at a lost on question 3 on HW3? I have no idea how to do this proof by construction. BTW, if anyone is interested in doing hw together, study for exams, etc., feel free to IM me using AIM (jzulu88).

Date Stamp :- Wednesday, February 05, 2003 at 00:17:45 (CST)
From :-Tazeen
Subject :-Hw 3 2a
Comments:- Whenever you're asked for a NDFSM, giving a DFSM is fine. However if you're asked for a DFSM, make sure that it's not a NDFSM.

Date Stamp :- Tuesday, February 04, 2003 at 23:08:11 (CST)
From :-James
Subject :-HW3 - 2a
Comments:- Is it okay if we have a DFSM, instead of a NDFSM, since they're equivalent anyways? I'm finding that it's easier to build a DFSM for question 2a, than building a NDFSM. Did I miss something? I think the symbol between n and m was defined in HW1. It means n mod 3 = m mod 3.

Date Stamp :- Tuesday, February 04, 2003 at 17:32:57 (CST)
From :-Jay
Subject :-HW3 question 2a
Comments:- What does the operator between n and m mean?

Date Stamp :- Sunday, February 02, 2003 at 14:02:33 (CST)
From :-Tazeen
Subject :-HW3 1e
Comments:- 000 would be two pairs of consecutive 0's so it shouldn't be accepted by the FSM, neither should 111.

Date Stamp :- Saturday, February 01, 2003 at 05:51:33 (CST)
From :-Damon
Subject :-HW 3
Comments:- On problem 1e, would 111 or 000 be legal inputs?

Date Stamp :- Thursday, January 30, 2003 at 10:54:20 (CST)
From :-Tazeen
Subject :-Max
Comments:- Just read the last part of the question, even after multiple posts! Max(a*b*) = {} because take any string in a*b* you can always put something to its right side to get another string in a*b*.
Max(ab*a) = ab*a because given any string in the language there's nothing you can put to its right side to get another string in the language, every string starts with a single a and ends with a single a


Date Stamp :- Wednesday, January 29, 2003 at 18:49:48 (CST)
From :-Tazeen
Subject :-Leading 0s
Comments:- Just a 0 is okay. 00 would have a leading 0 and is not allowed.

Date Stamp :- Wednesday, January 29, 2003 at 18:48:48 (CST)
From :-Tazeen
Subject :-Max
Comments:- Example L = { abb, a, ba}. Then Max(L) = {abb, ba}
Consider each string in L, lets call it m, if there's no string n (other than epsilon) such that mn is an element of L, then m is in Max(L).
So look at the first string in L, it is abb, there's nothing you can concatenate to its right side to get another string in L, so it's in Max(L).
The second string in L is a, you can concatenate bb to its right side to get abb which is in L, so a will not be in Max(L).
The third string in L is ba, there's nothing you can concatenate on its right side to get another string in L. so it's in Max(L).
Hope that helps..

Date Stamp :- Wednesday, January 29, 2003 at 18:38:15 (CST)
From :-Tazeen
Subject :-Closure
Comments:- The closure includes the resulting set and the original set.

Date Stamp :- Wednesday, January 29, 2003 at 17:32:46 (CST)
From :-Jason
Subject :-Closure
Comments:- When looking for the closure of a set under an operation, does the closure contain members from the resulting set only or does it contain members from the original set too?

Date Stamp :- Wednesday, January 29, 2003 at 14:25:19 (CST)
From :-Kendell Zahn
Subject :-Oops
Comments:- Sorry about all those postings folks... I was trying to make the posting more readable, didn't realize it was reposting everytime... Guess it will get some attention now though :)

Date Stamp :- Wednesday, January 29, 2003 at 14:23:54 (CST)
From :-Kendell Zahn
Subject :-What does Max do?
Comments:- I have an explanation of my problem on the newsgroup, but I am also having trouble understanding Max. I might have misunderstood something written down on the board to be the answer. Are these the correct answers: Max(a*b*) = [empty set], and Max(ab*a) = ab*a -- Thanks!

Date Stamp :- Wednesday, January 29, 2003 at 14:23:20 (CST)
From :-Kendell Zahn
Subject :-What does Max do?
Comments:- I have an explanation of my problem on the newsgroup, but I am also having trouble understanding Max. I might have misunderstood something written down on the board to be the answer. Are these the correct answers: Max(a*b*) = [empty set] Max(ab*a) = ab*a Thanks

Date Stamp :- Wednesday, January 29, 2003 at 14:22:18 (CST)
From :-Kendell Zahn
Subject :-What does Max do?
Comments:- I have an explanation of my problem on the newsgroup, but I am also having trouble understanding Max. I might have misunderstood something written down on the board to be the answer.

Date Stamp :- Wednesday, January 29, 2003 at 00:01:08 (CST)
From :-James
Subject :-Leading zeros
Comments:- HW2 Q4: without leading 0's. But is it okay to have just one 0? I suppose that 0 doesn't count as "leading", since 0 is divisible by 4.

Date Stamp :- Tuesday, January 21, 2003 at 11:36:02 (CST)
From :-Tazeen
Subject :-Problem 6
Comments:- It would be okay to use a truth table. but the point of the question is to make sure everyone reviews stuff like commutativity, a => b is the same as not a or b, and so forth. The rules you'd need to use are in the background review material in dr. rich's notes, it's towards the back, maybe after the practice homeworks.

Date Stamp :- Monday, January 20, 2003 at 10:35:51 (CST)
From :-Ben
Subject :-Problem Session
Comments:- Will you be holding a problem session tonite, or not because of the holiday?

Date Stamp :- Tuesday, January 14, 2003 at 10:59:52 (CST)
From :-Tazeen
Subject :-Welcome
Comments:- Welcome to the discussion forum for CS341. This forum is designed for the students to communicate with each other. Feel free to ask questions and to answer them.