Automata...

A website that explain PDA...

2005-09-28T02:36:00.000-07:00

http://en.wikipedia.org/wiki/Pushdown_automata

Assignment # 3

2005-08-05T05:04:00.000-07:00

Dessign an algorithm that will explain yhe process of creating CNF.

Project Implementation The project is to implement the CYK algorithm on p 139-141 in text book.Your computer program, in the language of your choice, will
1) read a grammar as defined above from a file. (fixed name or command line)
2a) print the grammar from your internal data structure.
2b) print the grammar after converted to Chomsky Normal Form.
3) read a string of terminal symbols from the keyboard,
4) print the string that is read,
5) print "accepted" or "rejected" depending on the string being in the grammar or not being in the grammar.
Your program should loop back and read another string until end of file.i.e. keep repeating steps 3) 4) and 5) until end of file.

Below are three grammars (pick 3 or 3a) and four strings for each grammar.Run them and turn in:
a) source code listing of your programb)
b) output from three runs (four if you did variable with digits)

But, you need Chomsky Normal Form
The CYK algorithm expects the grammar in Chomsky Normal Form,
that is: productions can be one of two formats A -> a or A -> BCThe grammars will have the "simplification" steps 1), 2) and 3) outof the way, that is 1) No useless variables, 2) No nullable variables and3) no unit productions. But, the grammars are not in Chomsky Normal Form,so, either convert the grammar by hand, YUK!, or program in theconversion of the raw grammar to Chomsky Normal Form.Step 4) of "simplification" is the following algorithm: 'length' refers to the number of variables plus terminal symbols on the right side of a production. Loop through the productions For each production with length greater than 1 do Replace each terminal symbol with a new variable and add a production new variable -> terminal symbol.
(An optimization is to reuse a variable name that has an existing production variable name -> terminal symbol and not add another production) Loop through the productions For each production with length grater than 2 do Replace two rightmost variables with a new variable and add a production new variable -> two rightmost variables.
(Repeat - either on a production or loop until no replacements.) Now the grammar, as represented by the productions, is in Chomsky Normal Form. proceed with CYK.
An optimization is possible but not required, for any two productions with the same right side, delete the second production and replace all occurrences of the second productions left variable with the left variable of the first production in all productions.
(This could be needed if you run out of upper case letters for variables.)

Assignment #2

2005-07-28T23:21:00.000-07:00

#2. Explain what is an ambigous grammar..
Ambiguous grammar
From Wikipedia, the free encyclopedia.
In computer science, a grammar is said to be an ambiguous grammar if there is some string that it can generate in more than one way (i.e., the string has more than one parse tree or more than one leftmost derivation). A language is inherently ambiguous if it can only be generated by ambiguous grammars.
For programming languages, ambiguous grammars can lead to difficulties for some compilers.
[edit]

Example
The context free grammar
A → A + A A − A a
is ambiguous since there are two leftmost derivations for the string a + a − a:

A
→ A + A

A
→ A − A

→ a + A

→ A + A − A

→ a + A − A

→ a + A − A

→ a + a − A

→ a + a − A

→ a + a − a

→ a + a − a
Equivalently, it is ambiguous since there are two parse trees for the string a + a − a:

The language that it generates, however, is not inherently ambiguous; the following is a non-ambiguous grammar generating the same language:
A → A + a A − a a
[edit]

Assignment #1

2005-07-28T23:07:00.000-07:00

#1. Personal Profile of Kleene..
http://www.brainyencyclopedia.com/encyclopedia/s/st/stephen_cole_kleene.html