DFA solved examples
Example 1: Draw a DFA for the language accepting strings ending with ‘0’ over input alphabets ∑={0, 1} ? Solution: Example 2: Draw a DFA … Read more
TOC
How do a DFA Process Strings?
The important thing about DFA is to know that it identifies the acceptance of strings. A DFA processes a string by starting in the start … Read more
Notations for DFA
Transition Diagram: A transition diagram for a DFA M = (Q, Σ, δ, q0, F) is a graph defined as follows: Transition Table:
Definition of Deterministic Finite Automata
A Deterministic Finite Automaton (DFA) consists of a finite set of states and a set of transitions from one state to another state on input … Read more
CNF from S–>aAD;A->aB/bAB;B->b,D->d.
RGPV 2020 Find the grammar in Chomsky Normal form equivalent to S–>aAD;A->aB/bAB;B->b,D->d. Ans. A context free grammar (CFG) is said to be in chomsky … Read more
NDFA accepting two consecutive a’s or two consecutive b’s.
RGPV 2020Construct a NDFA accepting all string in {a,b} with either two consecutive a’s or two consecutive b’s. Ans.
Regular expresion to CFG
To convert a regular expression to a context-free grammar (CFG), you can follow a set of standard conversion rules. Here are the rules for converting … Read more
Regular expression to Regular grammar
RGPV 2020 How can we construct regular grammar from regular expression? Ans. Lets take an regular expresion example: 0*(1(0+1))* Now convert above example in to … Read more
Grammar is ambiguous. S → aSbS|bSaS|∈
RGPV 2020 Show that the following grammar is ambiguous. S → aSbS|bSaS|∈ Ans. For grammar to be ambiguous, there should be more than one parse … Read more
leftmost and rightmost derivations
RGPV 2020 What are leftmost and rightmost derivations? Explain with suitable example ? Grammar: S → aS / ∈ For generating strings ‘aaa’. Left … Read more