Yioop - PHP Search Engine

[ Prev ]

2020-03-22

-- Mar 18 In-Class Exercise

Given S -> SS|(S)|a, convert to Chomsky Normal Form.

Step 1: New start variable

S0 -> S S -> SS|(S)|a

Step 2: remove ε rules

Skip this since there are on ε rules.

Step 3: Remove unit rules

S0 -> SS|(S)|a S -> SS|(S)|a

Step 4: Split up rules with RHS of length > 2

S0 -> SS|S1)|a S -> SS|S2)|a S1 -> (S S2 -> (S

Step 5: Correct format

S0 -> SS|S1S3|a S -> SS|S2S4|a S1 -> SS5 S2 -> SS6 S3 -> ) S4 -> ) S5 -> ( S6 -> (

(Edited: 2020-03-22)

Given S -> SS|(S)|a, convert to Chomsky Normal Form. Step 1: New start variable S0 -> S S -> SS|(S)|a Step 2: remove ε rules Skip this since there are on ε rules. Step 3: Remove unit rules S0 -> SS|(S)|a S -> SS|(S)|a Step 4: Split up rules with RHS of length > 2 S0 -> SS|S1)|a S -> SS|S2)|a S1 -> (S S2 -> (S Step 5: Correct format S0 -> SS|S1S3|a S -> SS|S2S4|a S1 -> SS5 S2 -> SS6 S3 -> ) S4 -> ) S5 -> ( S6 -> (

-- Mar 18 In-Class Exercise

(Edited: 2020-03-23)

((resource:20200323_152821.jpg|Resource Description for 20200323_152821.jpg))