Theory of Computing > QUESTIONS & ANSWERS > California State University, San Marcos CS 421 Theory of computing CS421 - Yoshii – HW3B (based  (All)

California State University, San Marcos CS 421 Theory of computing CS421 - Yoshii – HW3B (based on Week 10 - 11) – Other Practical Issues

Document Content and Description Below

California State University, San Marcos CS 421   Theory of computing CS421 - Yoshii – HW3B (based on Week 10 - 11) – Other Practical Issues Induction and CNF Always Use Black for your answ... ers DUE: Week 11 Friday before midnight TOTAL: 20 pts ** Name: **Qian Zhu -------------------------------------------------------------------------------------------------------------------------- 1) Proving that G matches L: [.5pts per prompt = 5pts] Finish the Inductive Proof from week 10. L = {w | w has an equal number of a’s and b’s} --------------------------------------------------------------------------------------------------------------------------- // we have 3 non-terminals 1 S -> aB // starts with a 2 S -> bA // starts with b // comes to A after starting with b. A means balance that b with a. 3 A -> a 4 A -> aS 5 A -> bAA // comes to B after starting with a. B means balance that a with b. 6 B -> b 7 B -> bS 8 B -> aBB We were doing induction to prove that G can generate all strings of L. GIVEN ASSUMPTIONS when |w| <= k-1 T1. S can =*=> w if w consists of an equal number of a's and b's T2. A can =*=> w if w has one more a than b's T3. B can =*=> w if w has one more b than a`s You must now prove the properties (T2 and T3) of A and B for the |w| = k step. Please fill in the template below. For Why questions, refer to the above given assumptions. E.g. “Using the given assumption T1.” T2 step for A: · Prove that if w has one more a than b's, A can =*=> w where |w| = k (describe w in terms of shorter strings z, y1 and y2) w looks like: a<z> or b<y1 and y2> [.5] Thus z and y1 and y2 have properties such that: z: <what does it have?>has equal a’s and b’s <how long is it?> k-1 each y1 and y2: <what does it have?>has two more a’s than b’s <how long is it?> k-1 What non-terminal can derive z? S Why? Based on the assumption on S. What non-terminal can derive each y? B Why? Based on the assumption on B. Thus A =*=> w: Starting with these rules from A: ** starts with a which follow by z or starts with b which follow y1 and y2 T3 step for B: · Prove that if w has one more b than a's, B can =*=> w where |w| = k Has to be done for the proof to be complete. But it is not required for this HW. -------------------------------------------------------------------------------------------- 2) Making it CNF – prep G for CYK parsing or analysis [15 pts] -------------------------------------------------------------------------------------------- We will start with 1. S -> a A B b 2. S -> e E Follow the following instructions step by step and answer each question. You may refer to the rule numbers in answering “which rules” questions! a) Remove all useless rules. [2pts] 1- Start bottom up from terminal strings.[1] o Which rules derive string o Which rules do not derive strings and should be removed 2- Then start top down from S.[1] o Which rules are reachable from S o Which rules are not reachable from S and should be removed b) Make it epsilon-free. [4pts] 1. S -> a A B b 5. B -> d d 1- Which non-terminals go directly or indirectly to epsilon (?? =*=> epsilon) [1] 2- Which rules use such non-terminals on the right side [1]?2 3- List all the ways to make such non-terminals disappear from the right side [1]. Newly added rules are: 4- What epsilon-rules will now be removed (they go directly to epsilon)[1]? 3 c) Make it chain-free (no <non term>-><non term>). [4pts] 1. S -> a A B b 2. S -> a B b 3. A -> C C 4. A -> C 5. C -> x 6. B -> d d 1- List all chain derivations (i.e. <non-term> =*=> <non-term>)[1]: 2- For each chain, add rule(s) to skip the right side non-terminal [1]. List added rules: 3- Delete all chain rules. List the ones to delete [1]: 4- Did any rule become useless and need to be removed? Which ones [1]? 2 d) Make it stratified (no non-terminal terminal mixture).[3pts] 1. S -> a A B b 2. S -> a B b 3. A -> C C 4. A -> x 5. C -> x 6. B -> d d 1. Add N#-><terminal> rule for each terminal (a,b,d,x) [1] (i.e. use N1, N2, etc.): 2. Stratify mixed rules. [1] Change this mixed rule: To what? Change this mixed rule: To what? Change B -> d d to what? 3. List the resulting grammar: [1] (should have only one terminal or only non-terminals on the RHS) e) Make the result of (d), binary (i.e. 2 non-terms) [2pts] 1- Change this rule: To what? Change this rule: To what? 2- Final Result is: [Show More]

Last updated: 1 year ago

Preview 1 out of 5 pages

Reviews( 0 )

Recommended For You

 Economics> QUESTIONS & ANSWERS > California State University, San Marcos - ECO 201ECO 201 &amp; 202 Quizz (All)

preview
California State University, San Marcos - ECO 201ECO 201 &amp; 202 Quizz

2. Individual and market demand Suppose that Sam and Teresa are the only consumers of pizza slices in a particular market. The following table shows their annual demand schedules: Price Sam's Quan...

By Kirsch , Uploaded: Apr 29, 2020

$14

 Biology> QUESTIONS & ANSWERS > California State University, San Marcos BIOLOGY 3 Biology 3.3.5 Adaptation and Natural Selection (All)

preview
California State University, San Marcos BIOLOGY 3 Biology 3.3.5 Adaptation and Natural Selection

3.3.5 Practice: Adaptation and Natural Selection Practice Assignment Florida Biology Sem 2 (S2974161) Christopher Bianco Points possible: 25 Date: ____________ 1. Draw a lake and label the photic,...

By d.occ , Uploaded: May 11, 2021

$7

 Psychology> QUESTIONS & ANSWERS > California State University, San Marcos PSYCHOLOGY PSYC 392Midterm_1_Questions (All)

preview
California State University, San Marcos PSYCHOLOGY PSYC 392Midterm_1_Questions

Which formal, mathematical approach to modeling perception uses conditional probabilities and prior probabilities to determine whether a hypothesis is true, given a certain set of observations? Ba...

By Cheryshev , Uploaded: Apr 27, 2021

$8

 Computer Science> QUESTIONS & ANSWERS > CMSC 303 Introduction to Theory of Computation, VCU Virginia Commonwealth University - CMSC 303CMSC303_Spring2017_A5_fullsolutions (All)

preview
CMSC 303 Introduction to Theory of Computation, VCU Virginia Commonwealth University - CMSC 303CMSC303_Spring2017_A5_fullsolutions

CMSC 303 Introduction to Theory of Computation, VCU Spring 2015, Assignment 5 Solutions Due: Thursday, March 30, 2017 in class Total marks: 38 marks + 4 marks bonus for typing your solutions in LaT...

By Expert Tutor , Uploaded: Apr 02, 2021

$7

 Mathematics> QUESTIONS & ANSWERS > California State University, San Marcos MATHEMATIC MATHEMATIC 441 Suppose that X is uniform on [-pi,2pi] . Find the probability density function of Y=sin(X). (All)

preview
California State University, San Marcos MATHEMATIC MATHEMATIC 441 Suppose that X is uniform on [-pi,2pi] . Find the probability density function of Y=sin(X).

Question Suppose that X is uniform on [-pi,2pi] . Find the probability density function of Y=sin(X).

By Muchiri , Uploaded: Mar 23, 2021

$5

 *NURSING> QUESTIONS & ANSWERS > Disproving the Theory of spontaneous Generation (All)

preview
Disproving the Theory of spontaneous Generation

The germ theory states that microorganisms are responsible for causing disease. This theory was initially not widely accepted; instead many people believed that this disease was caused by demons or wa...

By Senpai , Uploaded: Jan 27, 2021

$20

 Philosophy> QUESTIONS & ANSWERS > PHIL 2310 124 Theory of Ethics. Quiz 5. Graded A (All)

preview
PHIL 2310 124 Theory of Ethics. Quiz 5. Graded A

Quiz Question 1 (1 point) Saved The Greatest Happiness Principle is the idea that something is morally good when... Question 1 options: We disregard the consequences of our actions, focusin...

By Kirsch , Uploaded: Jan 06, 2020

$4.5

 Philosophy> QUESTIONS & ANSWERS > PHIL 2310 124 Theory of Ethics. Quiz 6. Graded A (All)

preview
PHIL 2310 124 Theory of Ethics. Quiz 6. Graded A

PHIL 2310 124 Theory of Ethics Quiz Submissions - Reading Quiz 6 The results of your quiz are shown here. You have 15 minutes to view them. Question 1 1 / 1 point What is "specesism", according...

By Kirsch , Uploaded: Jan 06, 2020

$5

 Microeconomics> QUESTIONS & ANSWERS > California State University, San Marcos ECON 201 Micro Economics  ECO 201 & 202 Quizz 4 (All)

preview
California State University, San Marcos ECON 201 Micro Economics  ECO 201 & 202 Quizz 4

2. Individual and market demand Suppose that Sam and Teresa are the only consumers of pizza slices in a particular market. The following table shows their annual demand schedules: Price Sam's Quant...

By Kirsch , Uploaded: Oct 05, 2022

$9

 Child Learning and Development> QUESTIONS & ANSWERS > Jean Piaget - Stage Theory of Development (All)

preview
Jean Piaget - Stage Theory of Development

Jean Piaget - Stage Theory of Development how does Jean Piaget's correlate, complement, or contradict the role of play in children? how may Jean Piaget's perspectives influence reading? Answer & E...

By destinyd , Uploaded: Feb 09, 2023

$7

$9.00

Add to cart

Instant download

Can't find what you want? Try our AI powered Search

OR

GET ASSIGNMENT HELP
83
0

Document information


Connected school, study & course



About the document


Uploaded On

Nov 15, 2022

Number of pages

5

Written in

Seller


seller-icon
Kirsch

Member since 4 years

898 Documents Sold


Additional information

This document has been written for:

Uploaded

Nov 15, 2022

Downloads

 0

Views

 83

Document Keyword Tags

THE BEST STUDY GUIDES

Avoid resits and achieve higher grades with the best study guides, textbook notes, and class notes written by your fellow students

custom preview

Avoid examination resits

Your fellow students know the appropriate material to use to deliver high quality content. With this great service and assistance from fellow students, you can become well prepared and avoid having to resits exams.

custom preview

Get the best grades

Your fellow student knows the best materials to research on and use. This guarantee you the best grades in your examination. Your fellow students use high quality materials, textbooks and notes to ensure high quality

custom preview

Earn from your notes

Get paid by selling your notes and study materials to other students. Earn alot of cash and help other students in study by providing them with appropriate and high quality study materials.

WHAT STUDENTS SAY ABOUT US


What is Browsegrades

In Browsegrades, a student can earn by offering help to other student. Students can help other students with materials by upploading their notes and earn money.

We are here to help

We're available through e-mail, Twitter, Facebook, and live chat.
 FAQ
 Questions? Leave a message!

Follow us on
 Twitter

Copyright © Browsegrades · High quality services·