Question

CFG for a^i b^j where i != j and i != 2j

CFG for a^i b^j where i != j and i != 2j

Homework Answers

Answer #1

The idea is to split the given langauge into to sub languages and then find their union to get the CFG as union of CFG is also a CFG.

So, we consider the following possibilities,

(i) i < j

(ii) j < i < 2j

(iii) i > 2j

and then we find the grammar for each and then find their union to get our grammar.

Let our grammar be, S = S(i) | S(ii) | S(iii)

(i)

S(i) → aS(i)b | Bb
B→ Bb | ε

(ii)

S(ii)→ aCbS(ii) → aCb
C → aCb | D
D→ aaDb | aab

(iii)

S(iii)→ aA

A→ aaAbaA | ε

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Question 1. Let a = i + 2j − k and b = i − 3j...
Question 1. Let a = i + 2j − k and b = i − 3j + k (a) Find vectors v and w such that b=v+w where v is parallel to a, but w is perpendicular to a. (b) Recall that the area of a triangle is half the length of its base times its height. Find the area of the triangle with corners at the points (2,0,0), (3,2,−1) and (3,−3,1), and explain what this has to do with...
PDA for L = {a^i b^j | i<j} PDA for L = {a^i b^j | i>j}
PDA for L = {a^i b^j | i<j} PDA for L = {a^i b^j | i>j}
PDA for {a^i b^j i != j} PDA for {a^i b^j c^k, i = j or...
PDA for {a^i b^j i != j} PDA for {a^i b^j c^k, i = j or j = k} PDA for # of a's = # of b's PDA for # b's = twice # of a's
Are the vectors a = i + j − k, b = i − j +...
Are the vectors a = i + j − k, b = i − j + k, and c = i + j + k coplanar?
Find the volume of the box generated by the vectors: i, j + k,    and...
Find the volume of the box generated by the vectors: i, j + k,    and    i + 2j + k. Please show all work and do not use cursive. Thank you for your help!
Give a CFG that consists of strings where all a’s appear before b’s, all b’s appear...
Give a CFG that consists of strings where all a’s appear before b’s, all b’s appear before c’s, there are an equal number of a’s and c’s, and an even number of b’s. After construct a PDA for this CFG
Suppose ?(?,?)=??f(x,y)=xy, ?=(−4,−4)P=(−4,−4) and ?=3?+2?v=3i+2j. A. Find the gradient of f. ∇?=∇f=  ?+i+  ?j Note: Your answers should...
Suppose ?(?,?)=??f(x,y)=xy, ?=(−4,−4)P=(−4,−4) and ?=3?+2?v=3i+2j. A. Find the gradient of f. ∇?=∇f=  ?+i+  ?j Note: Your answers should be expressions of x and y; e.g. "3x - 4y" B. Find the gradient of f at the point P. (∇?)(?)=(∇f)(P)=  ?+i+  ?j Note: Your answers should be numbers C. Find the directional derivative of f at P in the direction of ?v. ???=Duf= D. Find the maximum rate of change of f at P. E. Find the (unit) direction vector in which the maximum rate...
Vector A = i + 2.0 j -k and vector B = -i + j -2.0k....
Vector A = i + 2.0 j -k and vector B = -i + j -2.0k. Find A dot B and the angle between them
A motorboat sets out at 10 am from a position (( 6i i 2j) km relative...
A motorboat sets out at 10 am from a position (( 6i i 2j) km relative to a marker bouy, and travels at a constant speed of 53 kmhh 1 to intercept a ship. The ship maintains a steady velocity vector (3i+4j) kmhh 1 and at 11 am is at a position (3i i j) km relative to the bouy. Find the velocity vector of the motorboat, the time of interception, and the position vector of the point of interception...
Consider the parameterized motion given by r(t)=3t^2i-2t^2j+(6-t^3)k. Where is the object at time t=1? What is...
Consider the parameterized motion given by r(t)=3t^2i-2t^2j+(6-t^3)k. Where is the object at time t=1? What is the velocity at t=1? What is the speed at t=1? How far does the object move from 0≤t≤1? Round your answer to 2 decimal places. * r, i, j, and k should all have vector arrows above them