California State University, San Marcos CS 421 Theory of computing - Yoshii – HW1C (based on week2b, week3b notes) Describing Languages, Derivation Paths, Type of Grammar, Automata

Document Content and Description Below

California State University, San Marcos CS 421 CS421 - Yoshii – HW1C (based on week2b, week3b notes) Describing Languages, Derivation Paths, Type of Grammar, Automata =========================... ================================================= DUE: Week 4 Friday before midnight (11:55) TOTAL: 20 pts ** Name ================================================================================ Review Questions- All even numbered Inter questions from week2b. [2pts per Inter = 10 pts] -------------------------------------------------------------------- ##Inter2* L^2 = LL = {a^n b^n a^m b^m | n >=0 and m>=0 } Why do we have to have m and not just n in L^2 ? Answer ##Inter4* Generate another sentence by starting with <sentence> and replacing it repeatedly by the left-side of the rules until you reach the terminals. Each time you use a rule to expand a non-terminal, write its number next to the non-terminal node. (give a parse tree) Answer ** ##Inter6* 1 S -> aSb 2 S -> epsilon - Give the derivation path for S =*=> aaaabbbb. For each =>, write the rule number used. E.g. =1=> Answer - What is the language L generated by this grammar (describe using a set former notation). Answer ##Inter8: 1 S -> a S a 2 S -> a (generates 2 a’s from opposite ends and end with a) - Give a set former description for the language. Answer ** L = {a^n | n>=1} - Give a derivation path for aaa. For each =>, write the rule number used. E.g. =1=> Anwser ##Inter10: 1. S -> aa A bb B (A and B are expanded independently) 2. A -> aa A 3. A-> epsilon (generates aa’s) 4. B -> bb B 5. B -> epsilon (generates bb’s) - Give a set former description for the language for the grammar. Answer - Give a derivation path for aabb. For each =>, write the rule number used. Answer ** S=> aaAbbB => aabbx Summary from week3b [10 pts] -------------------------------------------- Q1: For the picture from ##Inter2* and ##Inter3* of week3b must indicate 1. the grammar type name, 2. the language type name, 3. automaton type, (for the inner 2) 4. the compiler part (for the inner 2) in each circle as follows: [.5 per prompt = 6pts] Outer most circle: Next circle in it: Next circle in it: Inner most circle: Q2: [2pts] - An automaton is a conceptual model of a _ - Write the Trs to say “In state2, if you see ‘a’, go to state 3.   Q3: [2pts] - What is the difference between Deterministic Automaton and Nondeterministic Automaton in relation to Trs? **   [Show More]

Last updated: 1 year ago

Preview 1 out of 2 pages