47. Define an Empty string.
The string of zero length is called the empty string, denoted by ∈.
48. Define prefix and suffix of a string.
Prefix: If w = vy for some y, then v is a prefix of w.
Suffix: If w = xv for some x, then v is a suffix of w.
49. What do you mean by Lexicographics ordering?
The Lexicographic ordering of strings is the same as dictionary
ordering, except that shorter strings precede longer strings.
The Lexicograhic ordering of all strings over the alphabet {0,1} is ( ,
∈ 0,
1, 00, 01, 10, 11, 000, ... }
50. What is a Language?
Any set of strings over an alphabet Σ is called a Language.
51. Define Σ
* .
The set of all strings, including the empty string over an alphabet Σ is
denoted by Σ
* .
52. Define concatenation of languages L 1 and L 2 .
L L L
w
w x y
= ⋅ = ∈
= ⋅
1
2
{
;
*
Σ
for some x L
∈ 1 and y L
∈ 2 }
53. Define Kleene star.
Kleene star of a language L is denoted by L
* which is the set of all
strings obtained by concatenating zero or more strings from L.
L
w
w w
w k
*
*
{
:
= ∈
=
Σ
1 K
for some k ≥ 0 and some w 1 , w 2 , K w
L
k ∈ }
54. What is Boolean logic?
It is a system built with two values — True and False., represented
by 1 and 0.
55. What do you mean by Negation?
It means NOT operation, represented by ¬.
Example: ¬0 = 1 and ¬1 = 0.
56. What do you mean by conjunction?
It means the AND operation, represented by ∧.
57. What do you mean by Disjunction?
It means the OR operation, represented by ∨.
58. Sketch the truth table for Conjunction & Disjunction
A
B
C A B
= ∧
A
B
C A B
= ∨
0
0
0
0
0
0
0
1
0
0
1
1
1
0
0
1
0
1
1
1
1
1
1
1
Con junc tion
Disconjunction
56
Theory of Automata, Formal Languages and Computation