BloggerNF

Formal definition of Turing Machine (TM) A Turing machine is a 7-tuple, (Q, Σ, Γ, δ,  q 0 , q accept , q reject ), where Q, Σ, Γ are all finite sets and 1. Q is the set of states, 2. Σ is the input alphabet not containing the blank symbol  B , 3. Γ is the tape alphabet, where  B  ∈ Γ and Σ ⊆ Γ, 4. δ: Q × Γ→Q × Γ × {L, R} is the transition function, 5.  q 0  ∈ Q is the start state, 6. q accept  ∈ Q is the accept state, and 7. q reject  ∈ Q is the reject state, where q reject  !=  q accept . State Diagram Here, Q= {q 0 , q 1 , q 2 , q 3 } Σ= {a, b, c} Γ= {a, b, c, B} q s =  q 0 q accept   = {q 3 } q reject   = {   Ø  } δ is given by the following transition table Transition Table: Program #include<stdio.h> #define BlankSpace '\0' int main() {     char inpstr[50];     int head, state;     printf("Enter String: ");     scanf("%s",inpstr);     state=0;     head=0;     printf("\n&qu

Formal definition of Turing Machine (TM) A Turing machine is a 7-tuple, (Q, Σ, Γ, δ,  q 0 , q accept , q reject ), where Q, Σ, Γ are all finite sets and 1. Q is the set of states, 2. Σ is the input alphabet not containing the blank symbol  B , 3. Γ is the tape alphabet, where B ∈ Γ and Σ ⊆ Γ, 4. δ: Q × Γ→Q × Γ × {L, R} is the transition function, 5.  q 0  ∈ Q is the start state, 6. q accept  ∈ Q is the accept state, and 7. q reject  ∈ Q is the reject state, where q reject  !=  q accept . State Diagram Here, Q= {q 0 , q 1 , q 2 , q 3, q 4 } Σ= {0, 1} Γ= {0, 1, X, Y, B} q s =  q 0 q accept = {q 4 } q reject = { Ø } δ is given by the following transition table Transition Table: Program #include<stdio.h> #define BlankSpace '\0' int main() {     char inpstr[50];     int head, state;     printf("Enter String: ");     scanf("%s",inpstr);     state=0;     head=0;     pri

Formal definition of pushdown automaton (PDA) A pushdown automaton is a 6-tuple (Q, Σ, Γ, δ,  q 0 , F), where Q, Σ, Γ, and F are all finite sets, and 1. Q is the set of states, 2. Σ is the input alphabet, 3. Γ is the stack alphabet, 4. δ : Q × Σε × Γε→P(Q × Γε) is the transition function, 5.  q 0  ∈ Q is the start state, and 6. F ⊆ Q is the set of accept states. Alphabets Σε=∑ U {ε} and Γε=Γ U {ε} P( ) accounts for the non-determinism State Diagram Here, P = (Q, Σ, Γ, δ,  q 0 , F), where  Q = { q 1 ,  q 2 ,  q 3 ,  q 4 },   ∑ = {0, 1, #},  Γ= {0, 1, $}, q s = q 1 F = { q 1 ,  q 4 },   δ is given by the following transition table, cell entries are new state and TOS symbol pair, blank entries are ∅. Inputs are current state, input string and TOS symbols. Cell entries are new state and TOS symbol pair. Blank entries are ∅. Transition Table: Program #include<stdio.h> #define EOS '\0' #define SIZE