Month 8: Theory of Computation

Problem Set 3 Solutions - Mike Allen

- NPDAs
Construct non-deterministic pushdown automata to accept the following languages.

- {1
^{n}0^{n}| n>0} - {0
^{n}1^{2n}| n>=0} - {1
^{n}0^{n}| n>0} U {0^{n}1^{2n}| n>=0} - (0+1)* - {ww | w in {0,1}*} (complement of ww)

- {1
- DPDAs
Construct deterministic pushdown automata to accept the following languages.

- {10
^{n}1^{n}| n>0} U {110^{n}1^{2n}| n>0} - Binary strings tha contain an equal number of 1s and 0s.
- Binary strings with twice as many 1s as 0s.
- Binary strings that start and end with the same symbol and have the same number of 0s as 1s.

- {10
- CFGs
Construct context free grammars to accept the following languages.

- (2.4b) {w | w starts and ends with the same symbol}
`S -> 0A0 | 1A1`

A -> 0A | 1A | e - (2.4c) {w | |w| is odd}
`S -> 0A | 1`

A -> 0S | 1S | e - (2.4d) {w | |w| is odd and its middle symbol is 0}
`S -> 0 | 0S0 | 0S1 | 1S0 | 1S1` - {0
^{n}1^{n}| n>0} U {0^{n}1^{2n}| n>0}`S -> 0A1 | 0B11`

A -> 0A1 | e

B -> 0B11 | e - {0
^{i}1^{j}2^{k}| i!=j or j!=k}`S -> AC | BC | DE | DF`

A -> 0 | 0A | 0A1

B -> 1 | B1 | 0B1

C -> 2 | 2C

D -> 0 | 0D

E -> 1 | 1E | 1E2

F -> 2 | F2 | 1F2 - Binary strings with twice as many 1s as 0s.
`S -> e | 0S1S1S | 1S0S1S | 1S1S0S`

- (2.4b) {w | w starts and ends with the same symbol}
- Ambiguity
- Explain why the grammar below is ambiguous.
`S -> 0A | 1B`

A -> 0AA | 1S | 1

B -> 1BB | 0S | 0The grammar is ambiguous because we can find strings which have multiple derivations:

**S**

0**A**

0 0**AA**

00 1**S**1

001 1**B**1

0011 0 1

**S**

0**A**

0 0**AA**

00 1 1**S**

0011 0**A**

00110 1

- (extra credit)
- Demonstrate that G (see problem set) is ambiguous.
The ambiguity is primarly due to the following rules:

`IF-THEN -> if condition then STMT``IF-THEN-ELSE -> if condition then STMT else STMT`

If we start with an IF-THEN statement and substitute an IF-THEN-ELSE for the consequent, we get:

`if condition then if condition then STMT else STMT`However, if we start with an IF-THEN-ELSE clause and substitute an IF-THEN for the consequent, we get the same thing. So, it is ambiguous. Note that many real programming languages (such as C and Java) exhibit this exact ambiguity in their syntax.

- (extra credit)

- Explain why the grammar below is ambiguous.
- Converting to Normal Form
- Put the following grammar into Chomsky Normal Form.
`S -> A | AB0 | A1A`

A -> A0 | e

B -> B1 | BC

C -> CB | CA | 1BRemove all e rules

`S ->`**e**| A | AB0 | A1A |**B0**|**A1**|**1A**

A -> A0 |**0**

B -> B1 | BC

C -> CB | CA | 1BRemove unit rules

`S -> e |`**A0**|**0**| AB0 | A1A | B0 | A1 | 1A

A -> A0 | 0

B -> B1 | BC

C -> CB | CA | 1BConvert remaining rules into proper form

`S -> e | A0 | 0 | AS`_{1}| B0 | A1 | 1A

A -> A0 | 0

B -> B1 | BC

C -> CB | CA | 1B

**S**_{1}-> B0 | 1A`S -> e | A`**N**| AS_{0}_{1}| B**N**| A_{0}**N**|_{1}**N**A_{1}

A -> A**N**|_{0}**0**

B -> B**N**| BC_{1}

C -> CB | CA |**N**B_{1}

S_{1}-> B**N**|_{0}**N**A_{1}

**N**_{0}-> 0

**N**_{1}-> 1NOTE: We did not need to create a new start state because the given one did not appear in the right side of any rule.

- Convert the following grammar into an equivalent one with no unit productions and no useless symbols.
`S -> A | CB`

A -> C | D

B -> 1B | 1

C -> 0C | 0

D -> 2D | 2Converts to

`S ->`**0C**|**0**|**2D**|**2**| CB

A -> C | D

B -> 1B | 1

C -> 0C | 0

D -> 2D | 2A is now useless and can be removed.

- Put the following grammar into Chomsky Normal Form.
- Derivations in Chomsky Normal Form
- (2.19) Show that if G is a CFG in Chomsky normal form, then for any string w in L(G) of length n>=1, exactly 2n-1 steps are required for any derivation of w.
We begin with a single nonterminal ("S") and form the string by making substitutions according to the rules. Each rule of the form A->BC adds a new nonterminal, and each rule of the form A->a converts one nonterminal into a terminal. Since it takes n-1 steps to grow our string from the original nonterminal to n nonterminals, and then n steps to convert each of those nonterminals into terminals, it takes 2n-1 steps to derive a string of length n.

- (2.20) Let G be a CFG in Chomsky normal from that contains b variables. Show that if G generates some string using a derivation with at least 2
^{b}steps, then L(G) is infinite.L(G) is infinite if any nonterminal shows up in a reduction of itself because this indicates a loop in the grammar. In the largest possible derivation, starting with the start variable ("S") we replace it with two other variables and each of those are replaced with two other variables and so on. Since no variable can be repeated along any branch of the tree without creating a cycle, the tree will be depth b and will contain 2

^{b}-1 nodes. So, if a derivation requires 2^{b}or more steps, the grammar must contain a cycle and L(G) must be infinite.

- (2.19) Show that if G is a CFG in Chomsky normal form, then for any string w in L(G) of length n>=1, exactly 2n-1 steps are required for any derivation of w.
- Two Way PDAs
Show that the set {0

^{n}1^{n}0^{n}| n>0} is accepted by a 2-way PDA.This 2-way PDA works by moving right across the string to make sure it begins with 0

^{n}1^{n}. Then it moves left to the beginning of the 1s and continues to the right to check for 1^{n}0^{n}.