LANGUAGES

Question 1

What is ∑?

Answer 1

Alphabet

Question 2

What is an alphabet?

Answer 2

A specified FINITE set identified as ∑
e.g. ∑1 = {0,1,2,3,4,5,6,7,8,9} is a 10 element set of decimal digits,

Question 3

What is an element?

Answer 3

The symbols inside of an alphabet

Question 4

What is a string?

Answer 4

String of length n over alphabet ∑ is just an ordered n-tuple of elements of ∑ without punctuation.

e.g. ∑ = {a,b,c} then a, aa, aaab, are all strings of ∑

Question 5

Can a string be empty?

Answer 5

YES

Question 6

What is the identifier for empty string?

Answer 6

ε - null/empty set

Question 7

What is ∑*?

Answer 7

Known as kleene’s star, this symbolises a set of all strings of ∑
∑* are INFINITE even if ∑ is finite
e.g. if ∑ = {a,b,c} then a, ab, aaa, bbac ∈ ∑*

Question 8

What is an example of what ∑* is if ∑ = {a}?

Answer 8

∑* = {ε, a, aa, aaa, aaaa, aaaaaa, aaaaaa …}

Include the empty string!

Question 9

What is ∑* if ∑ = {} (empty set}?

Answer 9

∑* = {ε}

(empty string)

Question 10

How does concatenation of strings occur?

Answer 10

Join end-to-end where u, v ∈ ∑*

e.g. if u = ab, v = ra and w = cad,
then uvwuv = abracadabra

Question 11

How to find the length of a concatenated string?

Answer 11

length(uv) = length(u) + length(v)

Question 12

How would you concatenate to ε?

Answer 12

uε = u = εu

ε is a UNIT for string concatenation so will always return non ε value.

Question 13

How does bracketing affect concatenation?

Answer 13

It has no effect!

u(vw) = (uv)w = uvw

Question 14

What is a language?

Answer 14

Language (or formal language) over ∑ is a SET of strings in ∑*
- notated by L
- any L ⊆ ∑* determines a language over ∑
e.g. ∑ = {a,b} L could be {a,b,ab,aa,bb}

Question 15

What is a regular expression?

Answer 15

Provides a way to formally define a language by identifying what doesn’t belong in a language.
Built using finitely many applications of rules

Question 16

What are the syntax rules for regular expressions?

Answer 16

every symbol of a ∈ ∑ is a regular expression
every string ε is a regular expression
every set Ø is a regular expression

if r and s are regular expressions:
- r / s is a regular expression
- rs is a regular expression
- r* is a regular expression

Question 17

What are the string rules for regular expressions?

Answer 17

Assuming u is a string,
u matches a ∈ ∑ iff u = a
u matches ε iff u = ε
u does NOT match Ø
u matches r / s iff u matches r OR u matches r (choice)
u matches rs iff u = wv where w matches r and v matches s
u matches r* iff u matches ε OR u = u, uu, uuu, uuuu …H

Question 18

How to solve if strings are part of regular expressions?

Answer 18

• break down the expression
• if no choices match then must equal no

Question 19

How to write a language determined by a regular expression?

Answer 19

L(r) = {u ∈ ∑* | u matches r}

example: r = a | a(bb|bbb) |ba* ∑= {a,b}
then L(r) = {a, abb, abbb, b, ba, baa}