Advanced Theory of Computation | Languages | Context Free Grammar (CFG) | Regular Expression (RE) | Finite State Automata(FSA)
In this section, we share four topics Languages, Context Free Grammar (CFG), Regular Expression (RE), and Finite State Automata(FSA). All related materials are shared with you where you need them.
Table of the Content:-
Languages
All String Languages
All String (a+b)* = { λ , a , b , ab , abb , abbb , aab , ………..}
Even Languages
Even Length =>
L = { ε , 2 , 4 , 6 , 8 , …….}
OR
L = { ε , aa , aaaa , aaaaaa , ……………………}
Odd Languages
Odd Values => L = { a , aaa , aaaaa , ………}
OR
L = { 1 , 3 , 5 , 7 , …….}
Prime Languages
Prime Length => L = { aa , aaa , aaaaa , aaaaaaa ………}
OR
L = { 2 , 3 , 5 , 7 , 11 , 13 …….}
Language (Formal and Informal )
Formal(Repeated, Syntatic)
e:g (Tanzeela) words are repeated
Informal (Non-Repeated, Semantic )
e:g ( Asif ) words are not repeated
Languages for Length Exactly Two
Range Exactly Two( Complete two digits )
Εx = { a , b}
L={aa , bb , ab , ba }
R = aa + bb + ab + ba
R = aa + ab + bb + ba
R = a(a+b) + b(b + a)
R = (a+b) (a+b)
Languages for Length at Least Two
At Least two( Minimum Two words and maximum more.. )
G = { a , b}
L={aab , aba , baa , ….. }
R.E = (a+b) (a+b) (a+b)*
Languages for Length at Most Two
Length at most Two( Minimum 1 and Maximum 2 words)
Ε = { a , b}
L={ ε , a , b , aa , bb , ab , ba }
= (ε + a + b ) (ε + a + b )
Lexicographic order
Let {a, b } be the alphabet set. Write all strings starting with b and having length 4 in lexicographic order.?
Sol:
R.E = b(a + b)*
L = { b , ba , bb , bbb , bab , baa , baaa , baab , baba , bbba , bbaa}
so our question is whether having length is 4 in lexicographic order.
Such as " baaa , baab , baba , bbba , bbaa "
................................................................................................................................................
Context Free Grammar (CFG)
Context Free Grammar (CFG) for ab*
Result Values
L = ab*
L = { a , ab , abb , abbb , abbbb , abbbbb , ………………………..}
The important note is mentioned at the end so plz must see it because this is your concept
Here we find all language esteems independently
To begin with, we track down how to get a ' a ' from this CFG so
S à a X …. 1st Eq
X à b X | ε ---- Second Equation
From 1st Eq
S à a X
So put X = ε in the first equation
a X
a ε so ε = 1
a
So here we find ‘ a ‘
First, we find how to get ‘ ab ‘ from this CFG so
From First Equation
S à a X
So put X = b X in first equation
a X
a b X so here again put X = ε
a b ε so here again put ε = 1
a b .1
ab
So here we find ‘ ab ‘
First, we find how to get ‘ abb ‘ from this CFG so
From First Equation
S à a X
a X So put X = b X in first equation
a b X
a b b X so here again put X = b X
a b b ε so here again put X = ε
a b b . 1 so here again put ε = 1
So here we find ‘ abb ‘
First, we find how to get ‘ abbb ‘ from this CFG so
From First Equation
S à a X
a X So put X = b X in first equation
a b X
a b b X so here again put X = b X
a b b b X so here again put X = b X
a b b b ε so here again put X = ε
a b b b .1 so here again put ε = 1
So here we find ‘ abbb‘
Also, different quantities of all dialects find with a similar example as the above notice
Note :
L = ab*
L =! { a , ba , babb , babbb , babbbb , babbbbb , ………………………..}
I say that always ‘ a ’ at the start point so ‘ b’ is not mentioned at the start.
Context Free Grammar (CFG) for (ab)*
 | |
Dry Run L = ( ab )* First, we understand and then create a language so ( ab )* so here we put power zero( 0 ) then ( ab )^0 = a^0.b^0 = 1.1 = 1 so ε = 1 Now we put power 1 then ( ab )^1 = a^1 . b^1 = ab Now again we put power 2 then ( ab )^2 = a^2 . b^2 = aa bb = aabb Now again we put power 3 then ( ab )^3 = a^3 . b^3 = aaa bbb = aaabbb So my language is L = { ε ,ab , aabb , aaabbb , aaaabbbb , aaaaabbbbb………………………..} OR L = { ε ,ab , abab , ababab , abababab , ababababab ………………………..} Note : L =! { ε , ba,bbaa,baba……………………………………………….} Here we find all language values separately First, we find how to get an ' a ' from this CFG so S à abS | ε …. First Equation Context Free Grammar (CFG) for a*b*
|
Context Free Grammar (CFG) for b*a*
 |
Context Free Grammar (CFG) for (a + b)*
Context Free Grammar (CFG) for a ( a + b )*
Contexts Languages = { a,aa,ab,, ………………………..}
Context Free Grammar (CFG) for ( a + b )*ab
L = { ab,aab,bab,aaab,abab,baab,bbab, ………………………..}
Context Free Grammar (CFG) for (a+b)*aa(a+b)*
Dry Run
L = ( a + b )*aa( a + b )*
In the first place, we see then make a language so
( a + b )*aa( a + b )* so here we put power zero( 0 ) then, at that point,
( a + b ) ^ 0 .aa. ( a + b ) ^ 0 = 1.aa.1 = aa
Presently we put power 1 then, at that point, ( a + b ) ^ 1.aa. ( a + b ) ^ 1 = aaaa or aaab or baab or baaa
Further, you create a language with this pattern
So my language is
L = { aa ,aaaa , aaab , baab , baaa………………………..}
Note: L =! { ε,……………………………………………….}
Context Free Grammar (CFG) for a*+b*
Here we create a language given below and you can check each through the above answer
L = { ε ,a ,b, aa , bb , ………………………..}
Context Free Grammar (CFG) for (a + ab)* + bb*
Here we create a language given below and you can check each through the above answer
Here one important point that is you can put values as power then mathematics formate use so your answer is accurate.
L = { ε, b ,ab, abb , ………………………..}
Context Free Grammar (CFG) for ab* + b*
Here we create a language given below and you can check each through the above answer
Here one important point that is you can put values as power then mathematics formate use so your answer is accurate.
L = { ε, a,b,ab, abb , ………………………..}
Context Free Grammar (CFG) for {a^nb^n | n ε N }
Context Free Grammar (CFG) for {a^nb^n | n ε W }
Context Free Grammar (CFG) for {a^nb^nc^n | n ε N }
Natural digit's ={1,2,3,4...............} n ε N
Language's L = { abc,aabcc ,abbbc ………………………..}
Context Free Grammar (CFG) {a^mb^n | m >n ε N }
Here we create a language given below and you can check each through the above answer
Here one important point that is you can put values as power then mathematics formate use so your answer is accurate.
N ={1,2,3,4...............} m > n ε N
L = { aab,aaabb ,aaaabb ………………………..}
Context Free Grammar (CFG) for a^2nb^n
Here we create a language given below and you can check each through the above answer
Here one important point that is you can put values as power then mathematics formate use so your answer is accurate.
L = { aab,aaaabb , ………………………..}
Context Free Grammar (CFG) for {a^mb^n | m >n & m ,n =0,1,2,….}
Natural ={ 0,1,2,3,4...............} m > n ε N
Teribe Language = { a, aa,aab ,aaabb ………………………..}
Context Free Grammar (CFG) for {a^mb^n | m < n & m ,n =0,1,2,….}
Natural Number =N ={ 0,1,2,3,4...............} m < n ε N
Combinatory Language = { b, bb,abb ,aabbb ………………………..}
Context Free Grammar (CFG) for a^mb^n
Here we create a language given below and you can check each through the above answer
Here one important point that is you can put values as power then mathematics formate use so your answer is accurate.
L = { abb, aabbb, ………………………..}
Context Free Grammar (CFG) for {a^mb^n | m ≠ n & m ,n =0,1,2,….}
Here we create a language given below and you can check each through the above answer
Here one important point that is you can put values as power then mathematics formate use so your answer is accurate.
W ={0,1,2,3,4...............} m ≠ n ε W
L = { a,b,abb, aab, ………………………..}
Context Free Grammar (CFG) for {a^mb^nc^m+n | m ,n =0,1,2,….}
L = { ε, ac,bc,abcc, ………………………..}
Context Free Grammar (CFG) for {a^mb^mc^n | m , n ε N }
Here we create a language given below and you can check each through the above answer
Here one important point that is you can put values as power then mathematics formate use so your answer is accurate.
L = { abc,abcc,aabbc, ………………………..}
Context Free Grammar (CFG) for {a^mb^nc^n | m , n ε N }
Context Free Grammar (CFG) for {a^mb^na^m | m , n ε N }
L = {aba ,abba,aabaa ………………………..}
Context Free Grammar (CFG) for an Equal Number of a’s and b’s
Equal Number of a’s and b’s (L) = { ε ,ab,ba,abab,baba,baab,abba, ……………..}
Context Free Grammar (CFG) for Un-Equal numbers of a’s and b’s
Context Free Grammar (CFG) for Palindrome
Here we create a language given below and you can check each through the above answer
Here one important point that is you can put values as power then mathematics formate use so your answer is accurate.
L = { λ, a,b,aa,bb,aaa,bbb,aba,bab, ………………………..}
Context Free Grammar (CFG) for Non-Palindrome
Here we create a language given below and you can check each through the above answer
Here one important point that is you can put values as power then mathematics formate use so your answer is accurate.
Here we follow top the answer
L = { ab , ba , aab , abb, bba ………………………..}
Context Free Grammar (CFG) for Language of All Palindrome(Even Length)
Languages for All Palindrome(Even Length) = { ε, aa , bb , abba , baab, …………..}
Context Free Grammar (CFG) for Language of All Palindrome(Odd Length)
Context Free Grammar (CFG) for Even String ((a+b)(a+b))*
Regular Expression (RE)
for
Regular Expression for Language of all those strings which end with ‘aa’ or ‘ab’ and have an odd length?
Ans:
R.E = (a+b)( (a+b)(a+b) )*(aa+ab)
OR
R.E = (a+b)( aa+ab)*
Ans:
R.E = (a+b)( (a+b)(a+b) )*(aa+ab)
OR
R.E = (a+b)( aa+ab)*
Regular Expression for Language of all those strings which do not contain substring ‘bb’?
Ans:
R.E = ( a+ba )*( ε + b )
Ans:
R.E = ( a+ba )*( ε + b )
Regular Expression for Language of all those strings whose length is odd and contains exactly one b?
Ans:
R.E = (aa)*b(aa)*+a(aa)*ba(aa)*
........................................................ ........................................................ ....................................................
Ans:
R.E = (aa)*b(aa)*+a(aa)*ba(aa)*
........................................................ ........................................................ ....................................................
Finite State Automata (FSA)
for.
FSA for End with "aa" or "ab" and have Odd length
FSA for End with "aa" or "ab" and have Odd length
|
FSA for End with "aa" or "ab" and have Odd length |
FSA for Don't contain Substring "bb"
 |
FSA for Length is Odd and End with "b"
FSA for String which has Ended with "b"
 |
0 Comments