Find Jobs
Hire Freelancers

Context Free Grammar, Chomsky Normal Form, Structural Induction

$10-30 USD

Cancelled
Posted almost 9 years ago

$10-30 USD

Paid on delivery
1)Let G be the context-free grammar E −→ ∅|e(epsilon)| 0 | 1 | (E ∪ E) | (E · E) | (E∗) where the underscored tildes are used to treat ∅and as terminal characters in the grammar. This grammar generates all regular expressions that refer to regular languages of binary strings—forcing parentheses on you makes them annoying to write but doesn’t affect the regular languages they denote. Define the “property of E” to be PE = “Every r I derive has a CFG Gr such that L(Gr) = L(r).” To get you rolling, here is the “SI” treatment of the first four rules, which collectively act asthe base cases, plus part of the fifth: 1. E → ∅: If E =⇒∗r using this rule first then L(r) = ∅, so we uphold PE by creating G∅ = (V, Σ, R, S) with V = { S }, Σ = { 0, 1 }, and R = ∅: no rules, no strings, so L(G∅) = ∅ as needed. 2. E → e: r =  so take Gr = G = S → . 3. E −→ 0: G0 = S → 0. 4. E −→ 1: G1 = S → 1. 5. E −→ (E ∪ E): Suppose E =⇒∗r using this rule first. Then r = s ∪ t where E ⇒∗s and E ⇒∗t. By IH PE on RHS (twice), there are context-free grammars Gs = (Vs, Σ, Rs, Ss) and Gt = (Vt, Σ, Rt, St) such that L(Gs) = L(s) and L(Gt) = L(t). Build a new CFG Gr = (Vr, Σ, Rr, Sr) by defining Vr = Vs ∪Vt ∪ { Sr } where Sr is a new start symbol with the new rules . . ........ Then L(Gr) = L(Gs) ∪ L(Gt) by construction, which equals L(s) ∪ L(t) by induction, which equals L(r) because r = s ∪ t, which upholds PE on LHS. 6. E −→ (E · E): 7. E −→ (E∗): 2)(b) Convert the following CFG into Chomsky normal form: S → RC | AT A → e(epsilon) | aA R → aRb | aA | bB B → e | bB T → bT c | bB | cC C → e | cC Note: This generates the strings in L(r), where r = a^∗ b^∗ c^∗, that do not have the numbers of a’s, b’s, and c’s all equal. If you take a regular expression r 0 for the complement of a^∗ b^∗ c^∗, and add a rule S −→ S(r0) as if you were carrying out problem (1) here, then you would literally get a context-free grammar G0 for the complement of the non-CFL language { a^n b^n c^n: n ≥ 0 }.
Project ID: 7433565

About the project

1 proposal
Remote project
Active 9 yrs ago

Looking to make some money?

Benefits of bidding on Freelancer

Set your budget and timeframe
Get paid for your work
Outline your proposal
It's free to sign up and bid on jobs
1 freelancer is bidding on average $25 USD for this job
User Avatar
hello. I saw your description and attached files. I understand it and can do it in 2 days. I have done several project like this. I'm an expert in Data Mining, Data Structures and Algorithms. And I know Java ,C/C++ and Python well. I'm interested this project. I want to discuss with you about this project. If it's possible,please contact me and explain more detail. I wait your good reply. Bye.
$50 USD in 1 day
5.0 (3 reviews)
1.8
1.8
User Avatar
i am confident enough that i can complete this project .i will finish it on time without any errors and flaws in it
$25 USD in 1 day
4.4 (1 review)
1.1
1.1

About the client

Flag of UNITED STATES
sheridan, United States
5.0
3
Payment method verified
Member since Dec 4, 2014

Client Verification

Thanks! We’ve emailed you a link to claim your free credit.
Something went wrong while sending your email. Please try again.
Registered Users Total Jobs Posted
Freelancer ® is a registered Trademark of Freelancer Technology Pty Limited (ACN 142 189 759)
Copyright © 2024 Freelancer Technology Pty Limited (ACN 142 189 759)
Loading preview
Permission granted for Geolocation.
Your login session has expired and you have been logged out. Please log in again.