Strings and Languages Flashcards
Describe alphabets and symbols
An alphabet is a non-empty finite set. For example the alphabet of decimal numbers is Σ={0,1,2,…,9}. You can also use the symbol Γ
The members of an alphabet are the symbols of the alphabet
Describe strings
A string written over an alphabet is a finite sequence of symbols from the alphabet written next to one another and not separated by a comma.
For example if Γ={0,2}; 02220 is a string over Γ
What is an empty string
A string of length zero. Denoted by ε or �(lambda)
Empty strings play the role of 0
What is a substring
String w is a substring of string z if w appears consecutively in string z
EG
cada is a substring of abracadabra
What is a language. And what is an infinite and finite language
A set of strings
Finite- finite number of strings; infinite-infinite number of strings
What is a formal language
A set of symbols and well defined rules by which symbols can be combined into entities known as scentences
What are the uses of formal languages
Used to model the grammar of programming languages (compilers), analyzing the structure of natural languages (syntax) and understanding what they mean (semantics)
what is ∑* and ∑+
∑* is the set of all strings (including ε ) on a an alphabet.
Eg
∑* on ∑={a,b} is
∑*= { 𝝀, a, b, aa, ab,ba,bb, aaa, aab ….}
∑+ denotes the set of non-empty strings and is given by
∑+=∑* -{ 𝝀}
Give examples of languages form ∑ = { a , b }. Use different formats for representing the languages
sEE 12
Describe concatenation and give some of its basic operations
Concatenating two strings, denoted by ◦, is done by writing one string the the right of the other. Eg is string u and v are u=ab and v=xy then the concatenation uv= abxy
1. If u is a string, then u^n stands for the string obtained by repeating u n times
2. Concatenation on a set ∑* is associative since for each u, v, w in ∑* u(vw) = (uv)w.
3. Identity element - The empty string is an identity element for the operation i.e. λu = uλ = u for all u in ∑* .
define the operations union, concatenation, and star on two languages A and B
A ∪ B={x|x ∈ A or x ∈ B}
A ◦ B={xy|x ∈ A and y ∈ B}
A∗={x1, x2,…, xk|k>0 and each xi ∈ A}
*sEE 23 FOR EXAMPLES
Describe L∗
L* is also called the Kleene Closure of L
Generally, the star operation (or closure of
language L) is denoted by: (see 22)
L* consists of all words formed by concatenating a
finite number of possibly zero, words/strings from
L
Describe L’
The complement of a language is defined with
respect to ∑* , that is the complement of L is
L’ = ∑* - L
In what scenario do we say a set is closed under some operation
A set is closed under some operation applying that operation on the members of the set returns an object still in the set
Let N = {1, 2, 3, . . . } be the set of natural
numbers
* When we say that N is closed under multiplication, we mean that for any x and y in N
,the product x × y also is in N .
* Comparatively, N is not closed under division, as
1 and 2 are in N but 1/2 (0.5 is not natural number) is not
