Chapter 12
Modeling Computation

© Ray Wisman

Resources

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/index.html - Index to the Rosen text Web site learning resources.

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/chapter12/extra_examples.html - Extra examples with solutions.

http://introcs.cs.princeton.edu/java/72regular/  - Overview of regular expressions and use.

http://www.regular-expressions.info - Good source on writing regular expressions.

 

12.1 Languages and Grammars

Important in computer science for formally describing programming languages (e.g. Java, C#, Python).

The first language to be compiled, FORTRAN, required several man-years (some claim 18) to implement.

Today, an average student can largely implement a more sophisticated language such as Java in a one-semester compiler course.

How can that be so? Are today's students that much smarter than the founders of computer science?

Read on about the power of formal languages and their grammars.

 

Definition

Formal language is specified by a set of well-defined rules.

Grammar is the set of rules defining a language.

Question 12.1 - For the grammar above, which of the following are sentences?

1. the rabbit eats quickly
   
2. a rabbit eats hops
   
3. a large rabbit eats quickly

Question 12.2 - Parse the following.

1. the rabbit eats quickly
   
2. a rabbit eats hops
   
   

Phrase-Structure Grammar

Definition 1

Vocabulary (or alphabet) V is set called symbols.

Words (or sentence) over V is a string of finite elements of V.

Empty (or null) string denoted by λ, contains no symbols.

Language over V is subset of V*, the set of all words over V.

Definition 2

Phrase structure grammar G = (V, T, S, P) consists of: V = vocabulary of all symbols T = subset of V consisting of terminal elements. S = start symbol from V P = finite set of productions

Non-terminals (V-T) denoted by N.

Example

G = (V, T, S, P)

V = {a, b, A, B, S}

T = {a, b}

S is start symbol

P = {S → AB, A → a, B → b, B → bB}

 

Parse of ab       S       |      AB      /  \     a    b

Parse of abbb          S          |         AB        /    \        a     bB                  \               bB                   \                    b

Parse of aa fails          S          |         AB       /    ?       a       a

Parse of b fails          S          |         AB       ?    ?        b

Parse of ba fails          S          |         AB       ?    ?        b      a

Question 12.3.1

a fail?

abb fail?

 

Example

G = (V, T, S, P)

V = {a, b, A, B, S}

T = {a, b}

S is start symbol

P = {S → ABa, A → a, B → b, B → Bb }

Parse of aba        S        |      ABa      / |    a  b

Parse of abbba           S           |         ABa        /  |         a   Bb           /             Bb          /      b

Parse of abb fails         S         |       ABa      /  |  ?    a   Bb           /         b

Question 12.3.2

Give the parse tree of: abba

Give the parse tree of: bba

Must all valid strings begin and end in an a?

 

Definition 3

Directly derivable w0 ⇒w1 when production z0 → z1 of G = (V, T, S, P) w0 = lz0r and w1 = lz1r strings over V where lz0r is concatenation of strings l, z0, and r

Derivation is sequence of steps w0 ⇒w1⇒w2⇒ .... ⇒ wn

Example

G=(V, T, S, P)

V={2, 3, S, E, M, R }

T={ 2, 3 }

S is start symbol

P={ S → E, E → E+M, E → E*M, E → M, M → 1, M → 2, M → 3 }

1+2 from S        S        |        E        |       E+M     /  |  \        M   +   2    |    1

1+2+3 from S        S        |        E        |       E+M     /  |  \       E+M  +   3  / | \ M  +  2 |     1

1+2*3+1 from S            S            |            E            |           E+M         /  |  \           E*M  +   1      / | \    E+M *  3   / | \    M  +  2   |      1

Question 12.3

Give derivation (parse tree) for: 1*2

Give derivation (parse tree) for: 1*2+3

 

Definition 4

L(G) Language generated by G, G = (V, T, S, P) set of all strings of terminals derivable from stating state S

Example

G = (V, T, S, P)

V={S, A, a, b}

T={a, b}

S is start symbol

P={S → aA, S → b, A → aa}

L(G) = {b, aaa}

Derivations from S

S → b  S  |  b

S → aA     aA    /    \  a      aa

Example

G = (V, T, S, P)

V={S, 0, 1}

T={0,1}

S is start symbol

P={S → 11S, S → 0}

L(G) = {0, 110, 11110, 1111110, ...}

Derivations from S

S → 0  S  |  0

S → 11S       S       |     11S          \           0

S → 11S       S       |     11S          \        11S             \              0

S → 11S       S       |     11S          \         11S              \             11S                 \                  0

Example

Give the phrase-structure grammar G = (V, T, S, P) that generates the string set {0ⁿ1ⁿ | n=0, 1, 2, ...}

0010		n=0 generates λ, the empty string
0111		n=1 generates 01
0212		n=2 generates 0011

G = (V, T, S, P)

V={S, 0, 1}

T={0,1}

S is start symbol

P = {S → λ, S → 0S1}

L(G) = {λ, 01, 0011, 000111, ...}

Derivations from S

S → λ  S  |  λ

S → 0S1       S       |     0S1     / | \   0  λ  1

S → 0S1       S       |   00S11  /    |   \ 0  0S1   1     / | \   0  λ  1

 

Types of Phrase-Structure Grammars

Definition

Type 2 grammar (context-free) can have productions only of the form: w1 → w2 where w1 is a single symbol and not a terminal.

Type 3 grammar (regular) can have productions only of the form: w1 → w2 where w1 = A and w2 = aB or w2 = a where A and B are non-terminals and a is a terminal or with w1 = S and w2 = λ

Right regular grammar is a formal grammar G = (V, T, S, P) such that all the production rules in P are of one of the following forms:

B → a     where B is a non-terminal in V and a is a terminal in T
B → aC   where B and C are non-terminals in V and a is in T. Note that C is on right side.
B → λ     where B is a non-terminal in V and λ denotes the empty string, i.e. the string of length 0.

Example of a right regular grammar G = (V, T, S, P)

V = {S, A, a, b, c}

T = {a, b, c}

S is start symbol

P = {S → aS, S → bA, A → λ, A → cA }

Question 12.5.1

Is P below part of a right regular grammar?

P = {S → aA, A → λ, A → a }

 

Left regular grammar all rules obey the forms

A → a    where A is a non-terminal in V and a is a terminal in T
A → Ba  where A and B are non-terminals in V and a is in T. Note that B is on left side.
A → λ    where A is a non-terminal in V and λ is the empty string.

Example of a left regular grammar G = (V, T, S, P)

V = {S, A, a, b, c}

T = {a, b, c}

S is start symbol

P = {S → Sa, S → Ab, A → λ, A → Ac }

Question 12.5.2

Is P below part of a left regular grammar?

P = {S → Aa, A → λ, A → a }

 

Example

Give the phrase-structure grammar G = (V, T, S, P) that generates the string set {0^m1ⁿ | m, n ∈ N}

0010		m, n=0 generates λ, the empty string
0011		m=0, n=1 generates 1
0110		m=1, n=0 generates 0
0111		m=1, n=1 generates 01
0312		m=3, n=2 generates 00011

G=(V, T, S, P)

V={S, A, 0, 1}

T={0,1}

S is start symbol

P={S → λ, S → 0S, S → 1A, S → 1, A → 1A, A → 1 }

G is a regular grammar

L(G) = {λ, 0, 1, 01, 001, 0011, ...}

Derivations

0   S  /  \ 0   S        \         λ

111       S       |      1A         \         1A            \             1

0011       S       |      0S          \          0S             \            1A                \                 1

Question 12.5.3

Is the above a left or right regular grammar?

 

Derivation Trees

G=(V, T, S, P)

V={2, 3, S, E, M, R }

T={ 2, 3 }

S is start symbol

P={ S → E, E → E+M, E → M, M → M*R, M → R, R → 2, R → 3 }

Determine if 2*3+2 belongs to G.

2*3+2          S          |          E          |         E+M       /  |  \      M   +   R          |       |     M*R      2    / | \   R  *  3   |   2

Question 12.5.4

Give derivation (parse tree) for: 2*2+3*2

Does the parse tree maintain correct precedence of * and +?

 

Note G is a grammar that is left associative and defines * above + in precedence.

 

 

Backus-Naur Form (BNF)

Reinvented after 2500 years by John Backus, to describe the syntax of the first compiled language, FORTRAN. Modified by Peter Naur.

Commonly used to specify syntax of computer languages.

EBNF (Extended Backus-Naur Form) normally extends BNF to add iterative repetition to BNF's recursive.

XML DTD (Data Type Definition) defines grammar using EBNF.

Example

<letter> ::= a | b | c | ... |z                        <letter> is defined as a or b or c or ... or z

<digit> ::= 0|1|2|3|4|5|6|7|8|9

<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>

<unsigned> ::= <digit> | <unsigned> <digit>

<sign> ::= + | -

<signed> ::= <sign> <unsigned>

-42     <signed>     /           \ <sign>    <unsigned>  /               /          \ -       <unsigned>  <digit>               /                 \         <digit>              2            /           4

bc3z             <identifier>                /             \         <identifier>    <letter>             /             \              \     <identifier>   <digit>      z          /          \            \  <identifier> <letter>  3       /                 \ <letter>            c   / b

 

12.2 Finite-State Machines with Output

Computers are an example of a finite-state machine. The computer's fetch/execute cycle is a finite-state machine.

Example - Vending machine

R is pressing Red button for apple juice. O is pressing Orange button for orange juice. n is nothing output. Price is 30 cents. Any amount over 30 cents is immediately refunded. s6 is only state where a drink is output. Example    Input: 10, 25, R What are the states? s0, s2, s6, s0 What are the outputs? n, 5, apple juice   Question 12.6     Input: 5, 10, 25, O What are the states? What are the outputs?

 

Finite-State Machines with Outputs

Definition

Finite-state machine M=(S, I, O, f, g, s0) S = states I = input alphabet O = output alphabet f = transition function that assigns each (state, input) pair a new state g = output function that assigns each (state, input) pair an output s0 = initial state

Example

M=(S, I, O, f, g, s0) S = {s0, s1, s2, s3} I = {0, 1} O = {0, 1} f = Defined in Table 2 g = Defined in Table 2 s0 = s0

0, 1 is input, output When s0 and input 0    s1 next state and output 1 When s0 and input 1    s0 next state and output 0

Example - Find the output generated on input: 10011 Current State Input Output s0 1 0 s0 0 1 s1 0 1 s3 1 0 s1 1 1 s0     Question 12.7 - Give the table for input: 00001

 

Example - Find the output for input: 10101 Current State Input Output s0 1 0 s3 0 0 s1 1 1 s2 0 0 s3 1 0 s0

Example - Add two binary numbers

+ 0101 0111 ____ 1100

+ x y _ z

s0 state when carry in = 0 s1 state when carry in = 1

Current State Input xi yi Output zi s0 11 0 s1 01 0 s1 11 1 s0 00 1 s0

Question 12.8 - Give output for input x=0101 and y=0100.

+	0101     x 0100     y ____

12.3 Finite-State Machines with No Output

Finite-state machines are used in recognition of computer languages - along with many other applications - a computer is a finite state machine.

Finite-state machines with no output have final states indicating recognition of some language element.

 

Set of Strings

Definition 1

Concatenation of A and B A and B are subsets of V* AB, is set of all strings xy x a string in A y a string in B

Example

V* = {a, aa, b, bb, c, cc, ccc}

A = { a, aa }

B = { b, bb }

AB = {ab, abb, aab, aabb}

 

Definition (repetition)

An for n=0,1,2,... A0 = { λ } An+1 = AnA for n=0,1,2,...

Example

A = { a, b }

Find Aⁿ for n = 0, 1, 2, 3

A⁰ = {λ}

A¹ = A⁰A = {λ}A = {a, b}

A² = A¹A = {a, b}A = {aa, ab, ba, bb}

A³ = A²A = {aa, ab, ba, bb}A = {aaa, aba, baa, bba, aab, abb, bab, bbb}

 

Definition 2

A*, Kleene closure of A the set of 0 or more strings from A

Example

A = {a}

A⁰ = {λ}

A¹ = A⁰A = {λ}{a} = {a}

A² = A¹A = {a}{a} = {a, aa}

A³ = A²A = {a, aa}{a} = {a, aa, aaa}

A* = {aⁿ | n=0,1,2,...}

λ, aa, aaaa are members

B = {a, b}

B⁰ = {λ}

B¹ = B⁰B = {λ}{a, b} = {a, b}

B² = B¹B = {a, b}{a, b} = {aa, ab, ba, bb}

B³ = B²B = {aa, ab, ba, bb}{a, b} = {aaa, aab, aba, abb, baa, bab, bba, bbb}

B* = {(a U b)ⁿ | n=0,1,2,...}        a U b means either a or b

λ, aa, aaaa, abab, bbbb are members

Question 12.11

C = {c, d}

C³ =?

ccccccddddc ∈ C* ?

λ ∈ C* ?

 

Finite-State Automata

Definition 3

Finite-state automaton M=(S, I, f, s0, F) S = states I = input alphabet f = transition function that assigns each (state, input) pair a new state f : S x I → S s0 = initial state F = final states, a subset of S

Example

M=(S, I, f, s₀, F)

S = {s₀, s₁, s₂, s₃}

I = {0, 1}

f = Table 1

s₀ = s₀

F = {s₀, s₃}

Note: Either 0 or 1 input in state s2, next state is s0

 

Question 12.12 - Which inputs reach a final state for the finite-state automaton at right?

1. 11
   
2. 0000
   
3. 00110
   
4. 00111

 

 

 

 

Language Recognition by Finite-State Machines

Definition 4

Recognized or accepted by machine M=(S, I, f, s0, F) if it takes s0 to f(s0, x), a final state.

Language recognized or accepted, L(M), by machine M=(S, I, f, s0, F) is set of all strings recognized by M.

Example 5

Determine the language recognized by the following.

M1    s0 is only final state. L(M1) = {1n | n=0,1,2,...} M2    s2 is only final state. L(M2) = {1, 01} M3    s0      {0n} s3      {0n10x} L(M3) = {0n, 0n10x | n=0,1,2...}

Example 6

Construct a finite-state automata to recognize each of these languages.

1. the set of bit strings that begin with two 0s                            00111101
2. the set of bit strings that contain two consecutive 0s              1000
3. the set of bit strings that do not contain two consecutive 0s    101011
4. the set of bit strings that end with two 0s                               11000
5. the set of bit strings that contain at least two 0s                     011101

Question 12.13 - Construct a finite-state automaton to recognize the set of bit strings that start with 01.

Hint: Similar to (a).

Question 12.14 - Complete the table for (e) above.

	f Input
State	0	1
s0	s1	s0
s1
s2

 

Note: Either 0 or 1 input in state s2, next state is s0

Nondeterministic Finite-State Automata

Deterministic finite-state automata must have a unique next state for a specific input.

Nondeterministic finite-state automata can have several next states for a specific input.

s₀ nondeterministic on 0 input whether next state is s₀ or s₂.

0001 input, states: s₀, s₀, s₀, s₂, s₄  (terminal state s₄)

Take the next state that eventually leads to s₄.

Example Determine if the nondeterministic finite-state automata recognizes:         001 Current State Input s0 0 s0 0 s2 1 s4

Question 12.15 - Does the above nondeterministic finite-state automata recognize:

1. 11
   
2. 01
   
3. 0011
   
4. 100

 

Definition 5

Nondeterministic finite-state automaton M=(S, I, f, s0, F) S = states I = input alphabet f = transition function that assigns each (state, input) pair a new state f : S x I → P(S) s0 = initial state F = final states, a subset of S

Example 9

Construct the diagram for the nondeterministic finite-state automaton given:

S = {s₀, s₁, s₂, s₃, s₄}

I = {0, 1}

f = Table 3

s₀ = initial state

F = {s₂, s₄}

Note that state s₀ has two possible next states on 0 input, s₀ and s₂.

Example 10

Find the language recognized by the above.

s₀ recognizes 0ⁿ

s₀, s₂, s₄ recognizes 0ⁿ01

s₀, s₁, s₄ recognizes 0ⁿ11

s₀, s₁, s₃  does not recognize since s₃ not a final state

L(M) = {0ⁿ, 0ⁿ01, 0ⁿ11 | n ≥ 0}

Example 11

Construct the diagram for the nondeterministic finite-state automaton given:

S = {s₀, s₁, s₂, s₃}

I = {0, 1}

f = Table 2

s₀ = initial state

F = {s₂, s₃}

Question 12.16.1 - Does the above nondeterministic finite-state automaton recognize:

1. 111
   
2. 11111
   
3. 10101
   
4. 1000

Question 12.16.2 - Draw the nondeterministic finite-state automaton diagram for the following table:

Theorem 1

If nondeterministic finite-state automaton M0 recognizes language L, then deterministic finite-state automaton M1 recognizes language L.

Example

 M₀ and M₁ recognize language L(M) = {0ⁿ, 0ⁿ01, 0ⁿ11 | n ≥ 0}

Question 12.17 - Do the above nondeterministic and deterministic finite-state automatons recognize:

1. 001
   
2. 1100

 

12.4 Language Recognition

Regular Expressions

Regular expressions are widely used in computing for recognizing patterns in strings, such in text editors or searching DNA for an enzyme sequence, e.g. GAATTC.

Overview of regular expressions and use: http://introcs.cs.princeton.edu/java/72regular/

Good source on writing regular expressions is: http://www.regular-expressions.info

Powerful patterns can be written using the minimum four operations:

1. concatenation        ab
   
2. logical or               (a | b)
   
3. replication             a+        a*
   
4. grouping               (a | b)*

Examples

Operation	Java Regular Expression	Match	No Match
One or more	a(bc)+de	abcde abcbcde	ade abc
Zero or more	a(bc)*de	ade abcbcde	abc bcbcde
Once or not at all	a(bc)?de	ade abcde	abc abcbcde
This or that	(a|b)	a cbd	c xyz
Character classes	[a-m]*	blackmail imbecile	above below
Negation of character classes	[^aeiou]	b c	a e
Exactly N times	[^aeiou]{6}	rhythm syzygy	rhythms allowed
Between M and N times	[a-z]{4,6}	spider tiger	jellyfish cow
Whitespace characters	[a-z\s]*hello	hello say hello	Othello 2hello

DNA words consist of 3 letters from the AGCT alphabet. Example words: ACT, GCT, CAT, TAC, AAA, CCC DNA strings start with ATG and end with TAA, TAG or TGA. Example string: ATGAAAGCTTGA   http://en.wikipedia.org/wiki/DNA_codon_table

Question 12.18.1 How many unique words can be generated? Think if it is a combination, permutation, addition or multiplication rule. Write a regular expression to match the start ATG codon. Write a regular expression to match the start ATG codon and stop codon (TAA, TAG, or TGA) from a DNA string. Ignore all errors in between. Write a regular expression to match the coding sequence for a DNA string. Start with the ATG codon followed by valid words and end with a stop codon (TAA, TAG, or TGA). Remember DNA consists of 3-letter words.

Regular expression tester (does not work with starting ?)

Regexp: String:

Replace: Result:

 

Regular expressions are a part of modern programming languages:

public class RegexValidate {    public static void main(String[] args) {        String regex = args[0];        String string = args[1];        System.out.println(string.matches( regex ));    } }

Example (command line execution)

java RegexValidate "a*|(a*ba*ba*ba*)*" abbbaaa

true

 

Regular Sets

Type 3 grammar (regular) can have productions only of the form: w1 → w2 where w1 = A and w2 = aB   or  w2 = a where A and B are non-terminals and a is a terminal or with w1 = S and w2 = λ

Regular set iff it is generated by a regular grammar. Operations of: concatenation, union (OR), Kleene closure Starting with empty set, empty string and singleton sets.

Regular expressions over set I (alphabet) defined by: ∅ is a regular expression λ is a regular expression x is a regular expression, x ∈ I (AB) concatenation, (A U B) union, in either A or B  A* Kleene closure, are regular expressions when A and B are regular expressions

Example 1

Strings in the regular sets can be specified by regular expressions.

Alphabet I = {0, 1}

Example 2

Find a regular expression that specifies each of these sets:

1. set of bit strings with even length
   
       (00 U 01 U 10 U 11)*

   Examples:    00, 0011, 1111
   

2. set of bit strings ending with a 0 and not containing 11
   
       (0 U 10)*(0 U 10)
   
   Examples:    0, 10, 001010
   
3. set of bit strings containing an odd number of 0s
   
       1*01*(01*01*)*

Examples:    0, 1111000

Question 12.18.2 - True or false

1. 1000 ∈ 10*
   
2. 000010 ∈ {0 U 10}*{0 U 10)
   
3. 10101 ∈ {0 U 10}*{0 U 10)
   
4. 1110001 ∈ 111(00 U 01 U 10 U 11)*

 

Kleene's Theorem

Set regular iff recognized by a finite-state automaton.

Finite-state automata to recognize concatenation, union and Kleene closures.

(a) M_AB or concatenation

(b) M_AUB or union

(c) M_A* or Kleene closure

 

Example 3

Construct a nondeterministic finite-state automaton that recognizes the regular set 1* U 01.

1* based on M_A* or Kleene closure

01 based on M_AB or concatenation

1* U 01 based on M_AUB or union

Figure (b) is equivalent to the automata constructed in (a) using M_AB, M_AUB, and M_A* but simpler.

 

Regular Sets and Regular Grammars

Regular set iff it is generated by a regular grammar. Operations of: concatenation, union (OR), Kleene closure Starting with empty set, empty string and singleton sets.

Theorem 2

Regular set iff generated by a regular grammar.

Method for constructing equivalent nondeterministic finite-state automaton M from regular grammar G.

Transitions of M from productions in G

s_F a final state.

s_A and s_B are not final states.

Input	Production in G	Transition in M	Diagram
λ	S → λ	sF
a	A → a	sA to sF
a	A → aB	sA to sB

Example 4

Construct a nondeterministic finite-state automaton M that recognizes the language generated by the regular grammar G:

G = (V, T, S, P)

V = {0, 1, A, S}

T = {0, 1}

P = {S → λ, S → 1A, S → 0, A → 0A, A → 1A, A → 1 }

Solution - By method in Theorem 2 proof

1. There is a state for each non-terminal symbol and a final state: S, A and final symbol

   S = s_s = s₀

   A = s_A = s₁

   Final = s_F = s₂

2. Transitions of M from productions P in G
   

   Input	Production in G	Transition in M	Productions P in G
   a	A → a	sA to sF	{ S → 0, A → 1 }
   a	A → aB	sA to sB	{ S → 1A, A → 0A, A → 1A }
   λ	S → λ	s0 final state	{ S → λ }

    

3. P = {S → λ, S → 1A, S → 0, A → 0A, A → 1A, A → 1    }

   S = s_s = s₀

   A = s_A = s₁

   Final = s_F = s₀, s₂

Production in G Input Transition in M   S → λ λ s0 S → 1A 1 s0 to s1 S → 0 0 s0 to s2 A → 0A 0 s1 to s1 A → 1A 1 s1 to s1 A → 1 1 s1 to s2 P = {S → λ, S → 1A, S → 0, A → 0A, A → 1A, A → 1    }

Question 12.19 - For the regular grammar:

G = (V, T, S, P)

V = {0, 1, A, S, B}

T = {0, 1}

P = {S → 0A, S → 1B, A → 0, B → 0,  B → 1B,  A → 1B }

given states for:

S = s_s

A = s_A

B = s_B

Final = s_F

Complete the table below for nondeterministic finite-state automaton M:

Production in G	Input	Transition in M
S → 0A	0	ss to sA
S → 1B	1	ss to sB
A → 0	0	sA to sF
B → 0	0
B → 1B	1
A → 1B	1

Question 12.20 - Using the table above, diagram a nondeterministic finite-state automaton that recognizes the language generated by the regular grammar.

 

Question 12.21 - For the regular grammar

G = (V, T, S, P)

V = {0, 1, A, B, S}

T = {0, 1}

P = {S → λ, S → 0A, S → 1, A → 0A, A → 1B, A → 1, B → 0 }

given states for:

S = s_s    A = s_A    B = s_B     Final = s_F

Complete the table below:

Production in G	Input	Transition in M
S → λ	λ	ss
S → 0A	0	ss to sA
S → 1	1	ss to sF
A → 0A	0
A → 1B
A → 1
B → 0

Question 12.22 - Using the table above, diagram a nondeterministic finite-state automaton that recognizes the language generated by the regular grammar.

 

Question 12.23 - For the regular grammar

G = (V, T, S, P)

V = {1, 2, 3, *, +, A, S}

T = {1, 2, 3, *, +}

P = {S → 1, S → 2, S → 3, S → 1A, S → 2A, S → 3A, A → *S, A → +S }

given states for:

S = s_s    A = s_A    Final = s_F

Complete the table below:

Production in G	Input	Transition in M
S → 1	1	ss to sF
S → 2	2	ss to sF
S → 3	3	ss to sF
S → 1A	1	ss to sA
S → 2A	2
S → 3A
A → +S
A → *S

Question 12.24 - Using the table above, diagram a nondeterministic finite-state automaton that recognizes the language generated by the regular grammar.

 

Example 5

Find a regular grammar that generates the regular set recognized by the finite-state automaton.

S = s0 A = s1 B = s2

G = (V,T,S,P) V = {0, 1, A, B, S} T = {0, 1} P = { S → λ S → 0A S → 1B S → 1 A → 0A A → 1B A → 1 B → 0A B → 1B B → 1   }

Question 12.25 - Find a regular grammar that generates the regular set recognized by the finite-state automaton.

 

 

A Set Not Recognized by a Finite-State Automaton

Example

Show that the set {0ⁿ1ⁿ | n=0, 1, 2, ...} is not regular.

1. Suppose the set is regular. Then there would be a recognizing nondeterministic finite-state automaton M.
2. Let N be the number of states, N = |S|. M must recognize 0^N1^N.
3. Let s₀, s₁, s₂,... s_2N be the sequence of states using the 0^N1^N symbols as input.  s_2Nis a final state.
4. Because only N states, pigeonhole principle states there must be at least two of first N+1 states must be the same. There is a loop from one state leading back to itself, the loop is length t.
5. A contradiction occurs because an input string of 0^N+t1^N would end in the final state s_2N. However, it is not of the form 0ⁿ1ⁿ so is not recognized by M.

 

 

The End