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 }.
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.