Formal Languages and regular langugaes IN FLAG

It is about Formal Languages and regular langugaes which is an important concept in autometa(FLAG).

2. FORMAL LANGUAGES : Derivations and the Language Generated by a
Grammar, Definition of a Grammar, Chomsky Classification of
Languages, Languages and their Relation, Recursive and Recursively
Enumerable Sets, Languages and Automata, Chomsky hierarchy of
Languages
REGULAR GRAMMARS : Regular Sets and Regular Grammars,
Converting Regular Expressions to Regular Grammars, Converting
Regular Grammars to Regular Expressions, Left Linear and Right Linear
Regular Grammars

8. Formal Language
A formal language L is a set of finite-length
words (or "strings") over some finite
alphabet A.  is the empty word.
Example:
A = {a, b, c}
L
1
= {ab, c}

11. Formal Languages - Examples
Some examples of formal languages:
•the set of all words over {a, b},
•the set { a
n
| n is a prime number },
•the set of syntactically correct programs in
some programming language, or
•the set of inputs upon which a certain
Turing machine halts.

12. Several operations can be used to produce new languages from
given ones. Suppose L1 and L2 are languages over some common
alphabet.
•The concatenation L1L2 consists of all strings of the form vw
where v is a string from L1 and w is a string from L2.
•The intersection of L1 and L2 consists of all strings which are
contained in L1 and also in L2.
•The union of L1 and L2 consists of all strings which are contained
in L1 or in L2.
•The complement of the language L1 consists of all strings over the
alphabet which are not contained in L1.
•The Kleene star L1* consists of all strings which can be written in
the form w1w2...wn with strings wi in L1 and n ≥ 0. Note that this
includes the empty string ε because n = 0 is allowed.

13. A formal language can be specified in a great
variety of ways, such as:
•Strings produced by some formal grammar (see
Chomsky hierarchy)
•Strings produced by a regular expression
•Strings accepted by some automaton, such as a
Turing machine or finite state automaton
•From a set of related YES/NO questions those
ones for which the answer is YES, see
decision problem

14. •If we select a string w such that w L, and
∈
w=xyz. Which of the following portions
cannot be an empty string?
a) x
b) y
c) z
d) all of the mentioned

15. • Let w= xyz and y refers to the middle portion
and |y|>0.What do we call the process of
repeating y 0 or more times before checking
that they still belong to the language L or not?
a) Generating
b) Pumping
c) Producing
d) None of the mentioned

16. Formal Grammar - Definition
A formal grammar G = (N, Σ, P, S) consists of:
•A finite set N of nonterminal symbols.
•A finite set Σ of terminal symbols that is disjoint from
N.
•A finite set P of production rules where a rule is of the
form
•string in (Σ U N)* -> string in (Σ U N)*
–(where * is the Kleene star and U is set union)
–the left-hand side of a rule must contain at least one
nonterminal symbol.
•A symbol S in N that is indicated as the start symbol.

18. •A regular language over an alphabet a is
one that can be obtained from
a) union
b) concatenation
c) kleene
d) All of the mentioned

32. •Answer in accordance to the third and last
statement in pumping lemma:
For all _______ xy
i
z L
∈
a) i>0
b) i<0
c) i<=0
d) i>=0

39. Closure properties of regular sets
•Property 1.
 
The union of two regular set is regular.
•Proof 
−
•Let us take two regular expressions
•RE
1 
= a(aa)* and RE
2 
= (aa)*
•So,
 L
1
 
= {a, aaa, aaaaa,.....} (Strings of odd length excluding Null)
•and
 L
2 
={ ε, aa, aaaa, aaaaaa,.......} (Strings of even length including
Null)
•L
1
 
L∪
2
 
= { ε, a, aa, aaa, aaaa, aaaaa, aaaaaa,.......}
•(Strings of all possible lengths including Null)
•RE (L
1 
L∪
2) = a*
 (which is a regular expression itself)
•Hence, proved.

40. Closure properties of regular sets
•Property 2. The intersection of two regular set is regular.
•Proof 
−
•Let us take two regular expressions
•RE
1 
= a(a*) and RE
2 
= (aa)*
•So,
 L
1
 
= { a,aa, aaa, aaaa, ....} (Strings of all possible lengths excluding
Null)
•L
2 
= { ε, aa, aaaa, aaaaaa,.......} (Strings of even length including Null)
•L
1
 
∩ L
2
 
= { aa, aaaa, aaaaaa,.......} (Strings of even length excluding
Null)
•RE (L
1
 
∩ L
2
) = aa(aa)* which is a regular expression itself.
•Hence, proved.

41. Closure properties of regular sets
•Property 3. The complement of a regular set is regular.
•Proof 
−
•Let us take a regular expression −
•RE = (aa)*
•So,
 L = {ε, aa, aaaa, aaaaaa, .......} (Strings of even length
including Null)
•Complement of
 
L 
is all the strings that is not in 
L.
•So,
 L’ = {a, aaa, aaaaa, .....} (Strings of odd length excluding Null)
•RE (L’) = a(aa)* which is a regular expression itself.
•Hence, proved.

42. Closure properties of regular sets
•Property 4. The difference of two regular set is regular.
•Proof 
−
•Let us take two regular expressions −
•RE
1 
= a (a*) and RE
2 
= (aa)*
•So,
 L
1 
= {a, aa, aaa, aaaa, ....} (Strings of all possible lengths
excluding Null)
•L
2 
= { ε, aa, aaaa, aaaaaa,.......} (Strings of even length including Null)
•L
1 
– L
2 
= {a, aaa, aaaaa, aaaaaaa, ....}
•(Strings of all odd lengths excluding Null)
•RE (L
1 
– L
2) = a (aa)* which is a regular expression.

43. Closure properties of regular sets
•Property 5. The reversal of a regular set is regular.
•Proof 
−
•We have to prove
 
L
R
 
is also regular if 
L 
is a regular set.
•Let,
 L = {01, 10, 11, 10}
•RE (L) = 01 + 10 + 11 + 10
•L
R
 
= {10, 01, 11, 01}
•RE (L
R
) = 01 + 10 + 11 + 10 which is regular
•Hence, proved.
•Property 6. The closure of a regular set is regular.
•Proof 
−
•If L = {a, aaa, aaaaa, .......}
 (Strings of odd length excluding Null)
•i.e.,
 RE (L) = a (aa)*
•L* = {a, aa, aaa, aaaa , aaaaa,……………}
 (Strings of all lengths excluding Null)
•RE (L*) = a (a)*
•Hence, proved.

44. Closure properties of regular sets
•Property 7. The concatenation of two regular sets is regular.
•Proof −
•Let
 RE
1 
= (0+1)*0 and RE
2 
= 01(0+1)*
•Here,
 L
1
 
= {0, 00, 10, 000, 010, ......} (Set of strings ending in
0)
•and
 L
2
 
= {01, 010,011,.....} (Set of strings beginning with 01)
•Then,
 L
1
 
L
2
 
=
{001,0010,0011,0001,00010,00011,1001,10010,.............}
•Set of strings containing 001 as a substring which can be
represented by an RE − (0 + 1)*001(0 + 1)*

45. •If L1, L2 are regular and op(L1, L2) is also
regular, then L1 and L2 are said to be
____________ under an operation op.
a) open
b) closed
c) decidable
d) none of the mentioned

46. •If L1′ and L2′ are regular languages, then
L1.L2 will be
a) regular
b) non regular
c) may be regular
d) none of the mentioned

47. Language of a Formal Grammar
The language of a formal grammar G = (N, Σ, P,
S), denoted as L(G), is defined as all those
strings over Σ that can be generated by starting
with the start symbol S and then applying the
production rules in P until no more nonterminal
symbols are present.

48. Language of a Formal Grammar
Example
Consider, for example, the grammar G with N =
{S, B}, Σ = {a, b, c}, P consisting of the
following production rules
1. S -> aBSc
2. S -> abc
3. Ba -> aB
4. Bb -> bb
This grammar defines the language {a
n
b
n
c
n
| n>0}

49. •Which of the expression is appropriate?
For production p: a->b where a V and
∈
b _______
∈
a) V
b) S
c) (V+∑)*
d) V+ ∑

50. CSE322
The Chomsky Hierarchy
Lecture #16

60. Chomsky's four types of grammars
•Type-0 grammars (unrestricted grammars)
languages recognized by a Turing machine
•Type-1 grammars (context-sensitive grammars)
Turing machine with bounded tape
•Type-2 grammars (context-free grammars)
non-deterministic pushdown automaton
•Type-3 grammars (regular grammars)
regular expressions, finite state automaton

61. Grammars, Languages, Machines
Type-0
Recursively enumerableTuring machineNo restrictions
Type-1
Context-sensitiveLinear-bounded αAβ -> αγβ
non-deterministic
Turing machine
Type-2
Context-freeNon-deterministic A -> γ
pushdown automaton
Type-3
RegularFinite state automatonA -> aB
A -> a

62. •The Grammar can be defined as: G=(V, ∑,
p, S)
In the given definition, what does S
represents?
a) Accepting State
b) Starting Variable
c) Sensitive Grammar
d) None of these

63. • Which among the following cannot be
accepted by a regular grammar?
a) L is a set of numbers divisible by 2
b) L is a set of binary complement
c) L is a set of string with odd number of 0
d) L is a set of 0
n
1
n

66. Type1

67. Type 1

68. •Production Rule: aAb->agb belongs to
which of the following category?
a) Regular Language
b) Context free Language
c) Context Sensitive Language
d) Recursively Ennumerable Language

69. Type 2

70. Type 3

71. •. The entity which generate Language is
termed as:
a) Automata
b) Tokens
c) Grammar
d) Data

72. Questions

73. Solution

74. • Let G be a grammar: S->AB|e, A->a, B->b
Is the given grammar in CNF?
a) Yes
b) No

75. •With reference to the process of conversion of a context
free grammar to CNF, the number of variables to be
introduced for the terminals are:
S->ABa
A->aab
B->Ac
a) 3
b) 4
c) 2
d) 5

76. Recursive and Enumerable Sets

77. Non Turing-Acceptable
Turing-Acceptable
decidable
Context-sensitive
Context-free
Regular
The Chomsky Hierarchy

78. Which of the following statement is false?
a) Context free language is the subset of context sensitive language
b) Regular language is the subset of context sensitive language
c) Recursively ennumerable language is the super set of regular language
d) Context sensitive language is a subset of context free language

79. LANGUAGES AND AUTOMATON

80. Recursive Sets
•Definition: A set S of natural numbers is called recursive (or decidable)
if there exists a Turing machine M such that, for any input x:
•If x S, the machine M halts and accepts x.
∈
•If x S, the machine M halts and rejects x.
∉
•Key Properties:
•Decidability: Recursive sets are decidable, meaning there is an
algorithm that always halts and decides whether an element
belongs to the set or not.
•Examples: Problems like determining if a string belongs to a
regular or context-free language fall into this category, since both
types of languages are decidable.
Recursive and Recursively Enumerable Sets

81. Recursively Enumerable (RE) Sets
•Definition: A set SSS of natural numbers is called recursively enumerable (or
semidecidable) if there exists a Turing machine M such that, for any input x:
•If x S, the machine M halts and accepts x.
∈
•If x S, the machine may either reject x or loop forever (i.e., it may not
∉
halt).
•Key Properties:
•Partial Decidability: RE sets are semidecidable, meaning the Turing
machine may confirm membership by halting and accepting, but it may
never halt for non-membership.
•Examples: The Halting Problem is a classic example of an RE set. Given a
Turing machine and an input, determining whether the machine halts on
that input is RE (it is enumerable but not fully decidable).

82. Relationship Between Recursive and RE Sets
•Every recursive set is also recursively enumerable (because if a Turing
machine can decide membership, it can also enumerate it).
•Not every recursively enumerable set is recursive. Some problems are
enumerable but not decidable because the machine might not halt for inputs that
do not belong to the set.

83. The Halting Problem
The halting problem, introduced by Alan Turing, asks the following
question:
Given a description of a computer program and an input, can we
determine whether the program will eventually stop (halt) or
continue to run forever (loop)?
Turing proved that there is no general algorithm that can solve this
problem for all possible program-input pairs. This means there are
some programs for which we can never know if they will halt or run
indefinitely.

84. 1. Automated Bug Detection in Software
•Scenario: You write a program, and you want to know if it will ever encounter a
condition where it enters an infinite loop.
•Problem: A program that gets stuck in an infinite loop will never halt, causing the
system to hang or crash.
•Real-Life Impact: Tools like static analyzers can detect some patterns that might
cause infinite loops, but due to the halting problem, there can never be a universal
tool that guarantees to detect infinite loops in all programs.
2. Artificial Intelligence (AI) Training
•Scenario: In machine learning, algorithms are trained on data to reach a certain
level of performance (accuracy, minimization of loss, etc.). Training continues until
the algorithm "converges" (reaches a good solution).
•Problem: There's no guarantee that a model will always converge. Sometimes,
training can go on indefinitely if the model is unable to find an optimal solution due
to the complexity of the data or algorithm.
•Real-Life Impact: AI researchers sometimes have to set arbitrary time limits on
training because they cannot predict whether or not the algorithm will ever stop
improving (halt) or just keep fluctuating (loop).

85. 3. Automated Task Scheduling
•Scenario: Imagine an operating system that schedules tasks like processing
multiple users' requests on a server.
•Problem: The system has to decide which tasks to execute and in what order,
but some tasks might never finish (e.g., they could be stuck in an infinite loop).
•Real-Life Impact: Task managers can force-kill processes that appear to be
stuck, but they can't always know in advance whether the process will halt or
not.

86. Why is the Halting Problem Important in Practice?
1.Limits of Computation: The halting problem shows that there are limits to what
computers can do. Even with all the computational power and algorithms available,
some problems are unsolvable in principle. This forces us to acknowledge that no
perfect bug-free, loop-free software can be guaranteed.
2.Error Handling in Systems: In critical systems (like aircraft control software or
hospital monitoring systems), it's vital to ensure the software won't freeze or loop
indefinitely. While engineers can't solve the halting problem, they design systems
to handle potential halts by adding timeouts, error handling, and watchdog timers.
3.Optimization Problems: In fields like logistics, resource allocation, or production
line management, algorithms are often used to optimize processes. However, due
to the halting problem, there's no guarantee that the best solution can always be
found in a finite time. This leads to the use of heuristic approaches or
approximation algorithms.
4.AI and Machine Learning: The halting problem reminds AI researchers that not
all training processes will result in a model that halts or reaches optimal
performance, and stopping criteria are often based on arbitrary limits (like a fixed
number of iterations).

88. Examples of Converting Regular Expressions to Regular Grammars
Example 1: Regular Expression a*
•Regular Expression: a* represents zero or more occurrences of the symbol a.
•Grammar:
•Non-terminal: S (start symbol)
•Production rules: S→aS
  ∣
ϵ This grammar generates any number of a's,
including the empty string.

89. Example 2: Regular Expression a(b c)
∣
•Regular Expression: a(b c)represents the concatenation of a followed by
∣
either b or c.
•Grammar:
•Non-terminals: S, A
•Production rules: S→aA ,A→b c This grammar generates strings like
∣
"ab" or "ac".

90. Example 3: Regular Expression (ab)*
Regular Expression: (ab)* represents zero or more occurrences of the string
ab.
•Grammar:
•Non-terminals: S, A
•Production rules: S→aA
  ∣
ϵ ,A→bS This grammar generates strings like
"", "ab", "abab", etc.
Example 4: Regular Expression a^+
•Regular Expression: a^+ represents one or more occurrences of a.
•Grammar:
•Non-terminal: S
•Production rules: S→aS
 a This grammar generates one or more a's (at ∣
least one a).