AUTOMATA THEORY PROJECT
Budget: $30 – $250 USD
CKY Parsing Project Requirements
1. Select the domain area of application and define its purposes by providing a list of 15-20 sentences related to the domain area of selection. For this purpose, give one paragraph description of specific domain in addition to those sentences. a. Travel management application
2. Perform logical design of the parser a. Build a Context Free Grammar (CFG) with 15-20 sentences/rules with moderate size (the average number of symbols on the right hand side of the productions are 3-5). b. Convert the CFG into another CFG in CNF c. For each sentence, build a CKY table to parse each sentence. Include 3 invalid sentences in addition to the 15-20 sentences in building the CKY tables. For example, if you have 15 sentences, then you will need to build 15 CKY tables for parsing the sentences. In addition, you will need to build another 3 CKY tables for 3 invalid sentences.
3. Perform physical design of the parser a. Select the right tool (i.e. any computer language of your choice) b. Write the parser code to implement the parsing A. Input to the parser: a sentence at a time B. Output from the parser: Yes/No (to indicate the sentence is accepted and valid, or not accepted and invalid)
4. Document the work. a. Title of the project b. Purposes/description c. CFG d. 15-20 valid sentences + 3 invalid sentences e. CFG converted into CNF f. CKY tables for all sentences including valid and invalid sentences g. Copy of the parser code h. Copy of execution snapshot for parsing of each sentence
PS: You don't need to write the parser code from scratch you can take any parser from the internet.
1. Select the domain area of application and define its purposes by providing a list of 15-20 sentences related to the domain area of selection. For this purpose, give one paragraph description of specific domain in addition to those sentences. a. Travel management application
2. Perform logical design of the parser a. Build a Context Free Grammar (CFG) with 15-20 sentences/rules with moderate size (the average number of symbols on the right hand side of the productions are 3-5). b. Convert the CFG into another CFG in CNF c. For each sentence, build a CKY table to parse each sentence. Include 3 invalid sentences in addition to the 15-20 sentences in building the CKY tables. For example, if you have 15 sentences, then you will need to build 15 CKY tables for parsing the sentences. In addition, you will need to build another 3 CKY tables for 3 invalid sentences.
3. Perform physical design of the parser a. Select the right tool (i.e. any computer language of your choice) b. Write the parser code to implement the parsing A. Input to the parser: a sentence at a time B. Output from the parser: Yes/No (to indicate the sentence is accepted and valid, or not accepted and invalid)
4. Document the work. a. Title of the project b. Purposes/description c. CFG d. 15-20 valid sentences + 3 invalid sentences e. CFG converted into CNF f. CKY tables for all sentences including valid and invalid sentences g. Copy of the parser code h. Copy of execution snapshot for parsing of each sentence
PS: You don't need to write the parser code from scratch you can take any parser from the internet.