FSM → CFL → Turing Machine
Language here is a set of Strings
a b c 0 1 2 4...
Third example is an \(\infin\) set
Let \(\Sigma = \{0,1\}\)
\(\epsilon\) denotes all strings of length 0
Cardinality of \(\Sigma^{n}=2^{n}\)
\(\Sigma^{*} = \Sigma^{0}\cup\Sigma^{1}\cup\Sigma^{2}\cup......\Sigma^{n}\)
=> \(\{\epsilon\}\cup\{0,1\}\cup.....\)
=> Set of all possible strinfgs of all length over \(\{0,1\}\) -> \(\infin\) set
Every DFA can be represented using 5 tuples \(\to (Q,\Sigma,q_{0},F,\delta)\)
For the Above DFA, the values are
0 | 1 | |
---|---|---|
A | C | B |
B | D | A |
C | A | D |
D | B | C |
Example Question: Let L1= Set of all strings that stras with 0 = {0,00,01,000,010,011,0000,....}. Design the DFA
Answer:
Here C is the Dead State of Trap State
Example Question: Construct a DFA that accepts sets of all strings over {0,1} of length 2.
Answer: \(\Sigma =\{0,1\}\) and \(L=\{00,01,10,11\}\)
Memory of FSM is very Limited and canno count strings
Union : \(A\cup B=\{x\mid x\in A \ or\ x\in B\}\)
Concatenation: \(A \circ B=\{xy\mid x\in A\ and\ y\in B\}\)
Star: \(A\ast=\{x_1,x_2,x_3\dots x_k\mid k\ge0 \ and \ each\ x_i\in A\}\)
Eg: \(A=\{pq,r\},B=\{t,uv\}\)
Ans:
Theorem 1: The class of Reglular Lanugauges is closed under Union(\(\cup\))
Theorem 2: The class of RL is closed under Concatenation(\(\circ\))
L={Set of all strings that end with 0}
If there is any way to run the machine that ends in any set of states out of which atleast one state is a final state, then the NFA accepts
For examples, check this video
Every DFA is an NFA, but not vice-versa. But there is an equivalent DFA for every NFA
Things to keep in mind
Example 1: Convert to DFA, L={Set of all strings over(0,1) that starts with 0}
Answer: \(\Sigma=\{0,1\}\)
Transition Table:
0 | 1 | |
---|---|---|
A | B | \(\phi\) |
B | B | B |
While converting this to DFA, we have to account the \(\phi\) as it should be converted to a dead state. This gives us the Transition Table,
0 | 1 | |
---|---|---|
A | B | C |
B | B | B |
C | C | C |
Which gives us the DFA, where C
is the dead state
To obtain the minimal version of any DFA which consists of the min number of states possible
Equivalent states can be combined
Two states can be equivalent if, \(\delta(A,X) \to F\) and \(\delta(A,X) \nrightarrow F\) OR \(\delta(B,X) \to F\) and \(\delta(B,X) \nrightarrow F\)
Where
X
is any i/p string
If \(|X| = n\) the A and B are said to be n
equivalent
Refer https://youtu.be/0XaGAkY09Wc for better Idea 😄