Hw$5$util:

Require Import Coq.Strings.Ascii.

Require Import Coq.Lists.List.

Import ListNotations.

Open Scope char$\_$scope.

Definition rule :$=($ascii $*$ list ascii$)\%$ type.

Structure grammar :$=\{$

grammar$\_$vars : list ascii;

grammar$\_$terminals : list ascii;

grammar$\_$rules : list rule;

grammar$\_$start : ascii;

$\}.$

Definition g$1$ :$=\{|$

grammar$\_$vars :$=["$C$"]$;

grammar$\_$terminals :$=["\{"$; $"\}"]$;

grammar$\_$start :$="$C$"$;

grammar$\_$rules :$=[$

$("$C$",["\{"$; $"$C$"$; $"\}"])$;

$("$C$",["$C$"$; $"$C$"])$;

$("$C$",[])$

$]$;

$|\}.$

Inductive Yield $($G:grammar$)$ : list ascii $->$ list ascii $->$ Prop :$=$

$|$ yield$\_$def:

forall u v w A w$1$ w$2,$

In $($A$,$ w$)($grammar$\_$rules G$)->$

w$1=$ u $++[$A$]++$ v $->$

w$2=$ u $++$ w $++$ v $->$

Yield G w$1$ w$2.$

Inductive Derivation $($G:grammar$)$: list $($list ascii$)->$ Prop :$=$

$|$ derivation$\_$nil:

Derivation G $[[$grammar$\_$start G$]]$

$|$ derivation$\_$cons:

forall u v ws$,$

Derivation G $($u :: ws$)->$

Yield G u v $->$

Derivation G $($v :: u :: ws$).$

Inductive Accept $($G:grammar$)$ : list ascii $->$ Prop :$=$

$|$ accept$\_$def:

forall w ws$,$

Derivation G $($w::ws$)->$

Forall $($fun c $=>$ List.In c $($grammar$\_$terminals G$))$ w $->$

Accept G w$.$

Hw$5$:

$(*$

#####################################################

### PLEASE DO NOT DISTRIBUTE SOLUTIONS PUBLICLY ###

#####################################################

$*)$

Set Default Goal Selector $"!".$

Require Import Coq.Strings.Ascii.

Require Import Coq.Lists.List.

Import ListNotations.

Open Scope char$\_$scope.

Require Import Hw$5$Util.

$(*---------------------------------------------------------------------------*)$

$(**$

Use $`$yield$\_$def$`.$

$*)$

Theorem yield$\_$eq:

forall G A w$,$ List.In $($A$,$ w$)($Hw$5$Util.grammar$\_$rules G$)->$ Hw$5$Util.Yield G $[$A$]$ w$.$

Proof.

Admitted.

$(**$

Use $`$yield$\_$def$`$ and $`$app$\_$assoc$`$ to correct the parenthesis.

$*)$

Theorem yield$\_$right:

forall G w$1$ w$2$ r w$3$ w$4,$ Hw$5$Util.Yield G w$1$ w$2->$ w$3=$ w$1++$ r $->$ w$4=$ w$2++$ r $->$ Hw$5$Util.Yield G w$3$ w$4.$

Proof.

Admitted.

$(**$

Similar proof than $`$yield$\_$right$`,$ but you should rewrite with

$`$app$\_$assoc$`$ after using $`$yield$\_$def$`,$ not before.

$*)$

Theorem yield$\_$left:

forall G w$1$ w$2$ l w$3$ w$4,$ Hw$5$Util.Yield G w$1$ w$2->$ w$3=$ l $++$ w$1->$ w$4=$ l $++$ w$2->$ Hw$5$Util.Yield G w$3$ w$4.$

Proof.

Admitted.

$(**$

Consider using one of the lemmas you have just proved.

When your goal is $`$In $("$C$",...)($grammar$\_$rules g$1)`,`$simpl; auto$`$

should solve it$.$

$*)$

Theorem g$1\_$rule$\_1$:

Hw$5$Util.Yield g$1["$C$"]["\{"$; $"$C$"$; $"\}"].$

Proof.

Admitted.

$(**$

Consider using one of the lemmas you have just proved.

When your goal is $`$In $("$C$",...)($grammar$\_$rules g$1)`,`$simpl; auto$`$

should solve it$.$

$*)$

Theorem g$1\_$rule$\_2$:

Hw$5$Util.Yield g$1["$C$"]["$C$"$; $"$C$"].$

Proof.

Admitted.

$(**$

Consider using one of the lemmas you have just proved.

When your goal is $`$In $("$C$",...)($grammar$\_$rules g$1)`,`$simpl; auto$`$

should solve it$.$

$*)$

Theorem g$1\_$rule$\_3$:

Hw$5$Util.Yield g$1["$C$"][].$

Proof.

Admitted.

$(**$

The proof should proceed by inversion and then case analysis on

string $`$u$`.$

$*)$

Theorem yield$\_$inv$\_$start:

forall G w$,$ Hw$5$Util.Yield G $[$Hw$5$Util.grammar$\_$start G$]$ w $->$ In $($Hw$5$Util.grammar$\_$start G$,$ w$)($Hw$5$Util.grammar$\_$rules G$).$

Proof.

Admitted.

$(**$

You will want to use $`$yield$\_$inv$\_$start$`.$ Recall that that $`$List$.$In$`$

simplifies to a series of disjunctions.

$*)$

Theorem g$1\_$ex$1$:

~ Hw$5$Util.Yield g$1["$C$"]["\{"].$

Proof.

Admitted.

$(**$

The idea is to use either: $`$yield$\_$left$`,`$yield$\_$right$`,$ or $`$yield$\_$def$`.$

$*)$

Theorem g$1\_$step$\_1$:

Hw$5$Util.Yield g$1["$C$"$; $"$C$"]["\{"$; $"$C$"$; $"\}"$; $"$C$"].$

Proof.

Admitted.

$(**$

The idea is to use either: $`$yield$\_$left$`,`$yield$\_$right$`,$ or $`$yield$\_$def$`.$

$*)$

Theorem g$1\_$step$\_2$:

Hw$5$Util.Yield g$1["\{"$; $"$C$"$; $"\}"$; $"$C$"]["\{"$; $"\}"$; $"$C$"].$

Proof.

Admitted.

$(**$

The idea is to use either: $`$yield$\_$left$`,`$yield$\_$right$`,$ or $`$yield$\_$def$`.$

$*)$

Theorem g$1\_$step$\_3$:

Hw$5$Util.Yield g$1["\{"$; $"\}"$; $"$C$"]["\{"$; $"\}"$; $"\{"$; $"$C$"$; $"\}"].$

Proof.

Admitted.

$(**$

The idea is to use either: $`$yield$\_$left$`,`$yield$\_$right$`,$ or $`$yield$\_$def$`.$

$*)$

Theorem g$1\_$step$\_4$:

Hw$5$Util.Yield g$1["\{"$; $"\}"$; $"\{"$; $"$C$"$; $"\}"]["\{"$; $"\}"$; $"\{"$; $"\}"].$

Proof.

Admitted.

$(**$

Use either $`$derivation$\_$nil$`$ or $`$derivation$\_$cons$`.$

$*)$

Theorem g$1\_$der$\_1$:

Hw$5$Util.Derivation g$1[["$C$"]].$

Proof.

Admitted.

$(**$

Use either $`$derivation$\_$nil$`$ or $`$derivation$\_$cons$`.$

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock

Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock

Step: 3 Unlock

Students Have Also Explored These Related Programming Questions!

Q:

Create two types of rows in your RecyclerView: a normal row and a row for more serious crimes. To implement this, you will work with the view type feature available in RecyclerView.Adapter. Add a new...

Q:

Require Import Coq.Strings.Ascii. Require Import Coq.Lists.List. From Turing Require Import Lang. From Turing Require Import Util. Import LangNotations. Import ListNotations. Import Lang.Examples....

Q:

Part-I Grade Class (60 marks) Given the following startup code of a Java class: 1. Adding Setter & Getter Methods of the following instance variables (25 marks) (a) quizzes (5 marks) (b) labs (5...

Q:

Java program that will read dates from an external text file and identify which two dates in the file have the fewest number of days between them and which two dates have the largest number of days...

Q:

To Do-List Application (Java) For this assignment, you will create an interactive To-Do (Task list) application using a PriorityQueue data structure. To-Do items or tasks have a priority associated...

Q:

Homework: HW Ch3 HW Score: 41.86%, 4.19 of 10 pts 4 of 7 (5 Score: 0.21 of 1 pt E3-26A (similar to) not the Alba's Debit 22,000 Property Tax Payable 11,500 HW Score: hours require r theData Table...

Q:

The resulting bar chart shows that when HMK is the AR Clerk and FKL is the Cash Receipts Clerk, CT is the GL Accounting Clerk for $226,851 of current AR balances. However, there are $25,352 of...

Q:

The resulting bar chart shows that when HMK is the AR Clerk and FKL is the Cash Receipts Clerk, CT is the GL Accounting Clerk for $226,851 of current AR balances. However, there are $25,352 of...

Q:

The resulting bar chart shows that when HMK is the AR Clerk and FKL is the Cash Receipts Clerk, CT is the GL Accounting Clerk for $226,851 of current AR balances. However, there are $25,352 of...

Q:

Can anybody follow the sample output to help me solve this Lab10.java? Thank u so much! CSE 110 Lab 10: Arrays LabExercise: Complete this portion of the lab during your labsession Tracking Sales The...

Q:

First Apple Computers Company manufactures one product. If its variable manufacturing cost is $18 per unit; total fixed manufacturing cost is $500,000: Required: 1) Calculate First Apple's total...

Q:

In the chapter, we stated that there are countless possible measures of process performance, many of which are derived from the four core measures quality, cost, time, and flexibility. In the...

Q:

Bernie Madoff ran a hedge fund that used money from newer investors to pay off older investors. Sam Bankman Fried ran a cryptocurrency exchange that did something similar. This is an example of _ _ _...

Q:

List the general guidelines for integrated assessment?

Previous Question Next Question