Cot 4210 Lecture Notes 3 By Njegos and Monika

Yüklə 465 b.
ölçüsü465 b.

COT 4210 Lecture Notes - 3

  • By Njegos and Monika

R is a regular expression if R is

Regular Expression

  • 0*10*:- zero or more 0’s followed by one 1 and followed by any number of 0’s or no 0

  • (0 U ε) 1*:- 0 followed by any number of 1’s or any number of 1’s

  • 1* Ø :- Take zero or more 1’s and concatenated by empty set. 1* Ø = Ø

  • Ø*:- {ε} ; Empty string

N1 U N2


0 U 1

(0 U 1)*

0 (0 U 1)* 0

0 U 0 (0 U 1)* 0


  • GNFA stands for Generalized Nondeterministic Finite Automaton.

  • GNFA are simply nondeterministic finite automaton wherein the transition arrows may have any regular expressions as labels, instead of only members of the alphabet.

Restricted GNFA

  • The start state has transition arrows going to every other state but no arrows coming in from any other state.

  • There is only a single accept state, and it has arrows coming in from every other state but no arrows going to any other state. Accept state is not the same as the start state.

  • Except for the start and accept states, one arrow goes from every state to every other state and also from each state to itself.


After Ripping Q3

  • If we have n states in DFA then restricted GNFA is going to have (n+2) states.

Yüklə 465 b.

Dostları ilə paylaş:

Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur © 2020
rəhbərliyinə müraciət

    Ana səhifə