LANGUAGES Flashcards
What is ∑?
Alphabet
What is an alphabet?
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,
What is an element?
The symbols inside of an alphabet
What is a string?
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 ∑
Can a string be empty?
YES
What is the identifier for empty string?
ε - null/empty set
What is ∑*?
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 ∈ ∑*
What is an example of what ∑* is if ∑ = {a}?
∑* = {ε, a, aa, aaa, aaaa, aaaaaa, aaaaaa …}
Include the empty string!
What is ∑* if ∑ = {} (empty set}?
∑* = {ε}
(empty string)
How does concatenation of strings occur?
Join end-to-end where u, v ∈ ∑*
e.g. if u = ab, v = ra and w = cad,
then uvwuv = abracadabra
How to find the length of a concatenated string?
length(uv) = length(u) + length(v)
How would you concatenate to ε?
uε = u = εu
ε is a UNIT for string concatenation so will always return non ε value.
How does bracketing affect concatenation?
It has no effect!
u(vw) = (uv)w = uvw
What is a language?
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}
What is a regular expression?
Provides a way to formally define a language by identifying what doesn’t belong in a language.
Built using finitely many applications of rules
What are the syntax rules for regular expressions?
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
What are the string rules for regular expressions?
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
How to solve if strings are part of regular expressions?
- break down the expression
- if no choices match then must equal no
How to write a language determined by a regular expression?
L(r) = {u ∈ ∑* | u matches r}
example: r = a | a(bb|bbb) |ba* ∑= {a,b}
then L(r) = {a, abb, abbb, b, ba, baa}
