Description
Find a regular grammar and expression
Unformatted Attachment Preview
HW 06-01 Regular Grammars
Problem 1
Find a regular grammar for each of the following regular expressions:
a. a + b
b. a + bc
c. a + b*
[optional] d. ab* + c
e. ab* + bc*
f. a*bc* + ac
g. (aa + bb)*
h. (aa + bb)(aa + bb)*
[optional]i. (ab)*c(a + b)*
Problem 5
Find a regular grammar to describe each of the following languages.
[optional] a. {a, b, c}
b. {aa, ab, ac}
[optional]c. {a, b, ab, ba, abb, baa, … , abn, ban, . . . }
d. {a, aaa, aaaaa, … , a2n+1, . . . }
[optional] e. {Λ, a, abb, abbbb, … , ab2n, . . . }
f. {Λ, a, b, c, aa, bb, cc, … , an, bn, cn, . . . }
g. {Λ, a, b, ca, bc, cca, bcc, … , cna, bcn, . . . }
h. {a2k | k ∈ ℕ} ∪ {b2k+1 | k ∈ ℕ}
i. {ambcn | m, n ∈ ℕ}
Problem 6
a. Find a regular expression to represent the set of all strings over the alphabet {a,b} that are of even length
b. Find a regular grammar to represent the set of all strings over the alphabet {a,b} that are of even length
Problem 7
a. Find a regular expression to represent the set of all strings over the alphabet {a,b} that contain the
substring aba
b. Find a regular grammar to represent the set of all strings over the alphabet {a,b} that contain the
substring aba
Copyright © 2024, Jennifer S. Kay, [email protected]
v. 42021110
Permission is granted to students currently enrolled in my classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Problem 8
[optional]
a. Find a regular expression to represent the set of all strings over the alphabet {a,b} that have an odd
number of a’s
b. Find a regular grammar to represent the set of all strings over the alphabet {a,b} that have an odd
number of a’s
Problem 13
Find a regular grammar for the following language: ab*cd
Problem 14
[optional] Find a regular grammar for the following language: abd*ef
Problem 15
Find a regular grammar for the following language: a*b*cd
Problem 16
[optional] Find a regular grammar for the following language: (a+b)*c (a+b)*
Problem Extra 06-01-01
Find a regular grammar for the language a+b
Problem Extra 06-01-02
Find a regular grammar for the language (ab*c)+(a*bc*)
Hint: Write one grammar for ab*c and another (using different non-Terminals) for a*bc* and then find a
way to combine them with a new start symbol
Copyright © 2024, Jennifer S. Kay, [email protected]
v. 42021110
Permission is granted to students currently enrolled in my classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Purchase answer to see full
attachment
