Sketch of Solutions to Exercises

2.3.1

(a)

1||-- -- |-- --|| oO -0||||| oO |||-||| 1[source]

(b)

Oo -|||a| -------|||- ----- ----- | - -a--- a-- -- -- - ----- -----b - - ---- ---- - - | --- b | -|| - - --|| eO ------------|- bOo - a - -c ---- |--- - - ----- ----- - - ----c ----c- -- - ----- -- -- - | --b------||| ------| | Oo c[source] (c)

Oo 0---||00 ---- 0Oo --- --| --1----| 0--- --|| Oo ---- |01 | -- | | --||- eOo 1|| | ---- | | --1 Oo | ---| 0---||10 | |1 | ---- || | 1Oo --- 0 || || --1----| || --|| Oo |11-- |- ||- -|| 1[source]

(d)

O ---1-|-- O --|| -------- | -1-------- | --||- oO ||-- 1 | |- |1 ----- || 1 --- O -|----- O 1[source]

(e)

||||||-||||| |||||||||| --| ||--||b||-|||-| ||- --||- even a ’s |||| |-| even a’s | -|even b ’s|-- |-|--|--|odd b’s|-- ||||||-|||| b |||||-|||| -| - -| - | - | |a a - |a a | | -||- - |- ||||||||| ||||||||| -|| ||--|b-||-||--| ||- - odd a’s |- | | odd a’s | --| |-||||-|-||-||| |-- even||b|’s| b odd|||b’s|[source]

(f)

-1||- -0||- - |- -- |-| --||- oO --0--|| oO |-1||||- oO -||||||| 1[source]

(g)

Oo --0--|- Oo 1||-- 0||- -|| 1 |- | -- |-| -- |-|1--- ||---- | || - | -0||||| 0 |||-- |-- | -- -1 | -- - Oo ||||||| 0Oo ----- - 00Oo ||| 1 | ------ 1 1 ---- | 1 -----|| 0 --- --| Oo ||-----11Oo 0[source]

(h)

0Oo |||- -- 0 -||--- ---0 --|||-1 --- |||||||--||| -|- ||| --||{01, 10}* - Oo -0,1 |||||||||||- -|- |||| --||1- 1 --- -||--| ---- 0 |||| -- 1Oo[source]

(i)

a,b,c|- a,b,c|- -| |-| -| |- || -- | e | |a|-||| ||a||||- e || - | --|| O -----|-q0O |||-||| q1O -|||||-|q2O -----|- Oo b c[source]

2.3.2

|0|-|- 0||-|- -||||||- ||||||-- -|-||||||- --|||||||- ---||||||| -|||||||| --|||- q ----1||-- q ---0-||--q ,q ---1-||-q , q | ||||0|||-- ||||1||- -||0|||1|- ----1|||2|- ||| || ||| ----- || || || 1|| ----- ||0 1 || ||1 |||||| |---- 1||||||| -|||||||| --|||||||||| --||||||||-|-- -| q2 ----0||--q0, q2 -| -q0,q1, q2| -0,1 |||||||| |||||||-- ||||||||-|||| -|-||||| 0[source]

2.3.3

S --> e --> aA --> aD --> bB --> a --> b A --> aA --> aD --> bB --> a --> b B --> aC C --> aD --> bB --> b D --> bB --> b

2.3.4

O |||-A| -- a -||---|| ---b ---||a | --- -|||| | -| --||- O | O S |||| b | ||-C | --||b | a -||--- |b --||--| | --||a b |||| -|||| Oo O B[source]

2.3.5 In each case an equivalent finite state automaton can be constructed. The finite state automaton will have a state corresponding to each nonterminal symbol.

Right Linear

The state corresponding to the start symbol is designated as an initial state. The finite state automaton has an additional state designated as an accepting state. For a production rule of the form A --> xB the finite state automaton has a sequence of transitions that starts at the state corresponding to A, ends at the state corresponding to B, goes through some new intermediate states, and consumes x.

A production rule of the form A --> x is considered in a similar manner. The only exception is that the sequence of transition rules is assumed to end at the accepting state.

Left linear

The state corresponding to the start symbol is designated as an initial state. The finite state automaton has an additional state that is designated as a start state. For a production rule of the form A --> Bx the finite state automaton has a sequence of transitions that starts at the state corresponding to B, ends at the state corresponding to A, goes through some new intermediate states, and consumes x.

A production rule of the form A --> x is considered in a similar manner. The only exception, is that the sequence of transition rules is assumed to start at the initial state.

Regular set ==> finite state automaton

Can be shown by induction.

Ø is accepted by || -- || O[source]

{e} is accepted by || -- || oO[source]

{a} is accepted by | a | --|| O -----|- oO[source]

L1(M 1) U L2(M 2) is accepted by ||||||| ||||||| |||||||| |- M |- -||q01O 1 qf1Oo ---- e--|||||||| ||||||||e- --- ||||||| --|| --||- O - | Oo ----e ||||||||||||||| e---|| ---||| ||||- - - O M2 Oo - -- -||q02 qf2 ||-- ||||||||||||||||||[source]

L1(M 1) . L2(M 2) is accepted by ||||||| ||||||| |||||||| |- M |- -||q01O 1 | Oo -- e--|||||||| ||||||||| --- ||||||| --||- O |e | Oo ||||||||||||||| e---|| --||| || ||||- - O M2 Oo - -- -||q02 ||-- ||||||||||||||||||[source]

(L(M ))* ||| -- - O || || || || |||e||||e||| |||||||| ||||||| -- O oO || -|| M1 |-- |||||||||||||||||||||[source]

Finite state automaton ==> regular set

omitted here