Regular Language Definition:
- The languages that can be represented by Regular Expressions are called Regular Languages
- The class of languages obtained by applying union, concatenation and kleene star for finitely many times on the basis elements (ϕ, ϵ , {a} ) are called Regular Languages
- The corresponding finite representations of Regular languages are called Regular Expressions.
- The language generated by Right Linear Grammar ( a type of Context free grammar with restrictions ) is Regular Language.
** All the Regular languages can’t be represented by Regular Expressions, so we use the tool called Grammars for representing the languages.
Linear Grammar :
- It is a special type of Context Free Grammar.
- A CFG G = (N, Σ, P, S) is said to be linear if every production rule of G has at most one non-terminal symbol on its righthand side.
Ex. S —> aSb ( Linear Grammar )
S —> AB ( Non-linear Gramar )
S —> aA ( Right Linear Grammar )
S —> Aa ( Left Linear Grammar )
*Note : A Right linear grammar or Left linear grammar is also called a Regular Grammar.
Testing Regular Languages:
======================
a) If it can be expressed using the Regular Expressions.
b) If it can be represented using Right linear Grammar.
=================================================================
1. Total number of sub strings present in "GATE" is
A)7 B) 10 C) 11 D) 8
Ans: 11
(n x (n+1) / 2 ) + 1
= ((4 * 5)/ 2) + 1
= 11
====================================================================
2. Number of trivial substrings in “GATE2013” are:
A. 37 B. 35 C. 2 D. 36
Ans : C
{} and "GATE2013"
=====================================================================
3. How many DFA with 4 state can be constructed over alphabet a and b with designated initial state?
Ans:
Initial state is fixed. Now from initial state, transitions for symbols a and b can be to any of the 4 states, so there are 4∗4=24 possibilities. Similarly, from 2nd, 3rd and 4th state, there are 24 possible transitions for each state i.e. we have 2^4∗2^4∗2^4∗2^4=2^16 possible transitions.
Each state also has 2 possibilities of being final state or not, so there are 2^4 possibilities for choosing final states.
So total number of DFAs = 2^16∗2^4=2^20.
========================================================================
Turing Machine:
- It is the kind of Automata which reads/writes the symbols on the tape and the control head can move left and right.
- It accepts the Recursively Enumerable Language
- It does not accept (Epsilon - e) moves.
- It may or may not halt (goes into infinite loop)
- If the string is found in the language then the TM halts at the final state
- If the string is not found then the TM halts at some other non final state.
- It can be thought of a FA with 2 stacks.
Example:
It may halt if the string in a language is accepted by the TM
It may halt if the string is not found in the language by the TM
It may enter infinite loop.
Halting Turing Machine:
- It always halts whether the string is found or not found in the Language
- The ™ doesn’t enter into infinite loop.
- It accepts the Recursive Language
Linear Bound Automata:
- It is a restricted TM in which the length of the tape is limited only to the input string.
- It is a halting TM
- It accepts the Context Sensitive Language
====================================================================
Unrestricted Grammar:
- It may have Epsilon - e productions
- The TM doesn’t accept e symbols on the tape.
Context Sensitive Grammar:
- It doesn’t have Epsilon - e productions
====================================================================
Recursively Enumerable Language:
- Recursively Enumerable languages are not closed under complementation.
Recursive Language:
- Recursive languages are closed under complementation.
Context Free Languages:
- Closed under Union, Concatenation and Kleene Closure
- Not closed under intersection and complementation.
Regular Languages:
- Closed under Union, Concatenation, Kleene Closure, intersection and complementation.
*Note : If L is a Context free language, L’ is both Recursive Language and RE Language.
====================================================================
Summary of all the Languages:
Recursively Enumerable Language ( ™ )
Recursive Language ( ™ )
Context Sensitive Language ( LBA )
Context Free Language ( PDA )
Deterministic Context Free Language ( DPDA)
Regular Language ( FA )
- All the languages have Membership Algorithm except the RE language since the ™ may enter into infinite loop.
========================================================================
No comments:
Post a Comment