Class: Falafel

Inherits:
Object
  • Object
show all
Defined in:
lib/falafel.rb

Overview

NFA to DFA DFA to REG Minimize DFA Remove epsilons from CFG Remove chaining from CFG Find a chomsky normal form fro CFG Apply CYK alogrithm on CFG and solve word problem

Direct Known Subclasses

DFA

Class Method Summary collapse

Instance Method Summary collapse

Class Method Details

.new {|instance| ... } ⇒ Object

Yields:

  • (instance) 


13
14
15
16
17
18
 
# File 'lib/falafel.rb', line 13

def self.new
  instance = allocate
  yield instance

  instance
end

Instance Method Details

#build(*args, states:, starts:, finals:) ⇒ Object 



20
21
22
23
24
25
26
27
 
# File 'lib/falafel.rb', line 20

def build(*args, states:, starts:, finals:)
  d_a, d_b    = args
  @delta_star = { a: d_a, b: d_b }
  @state_set  = power_set states
  @finals     = finals
  @states     = states
  @start      = starts
end

#cfg(alphabet, vars_set, start_var, rules) ⇒ Object 



113
114
115
116
117
 
# File 'lib/falafel.rb', line 113

def cfg(alphabet, vars_set, start_var, rules)
  require_relative 'cfg'

  CFG.new alphabet, vars_set, start_var, rules
end

#compose(lft, rgt) ⇒ Object

Concatenation two states Example: [[1, 2]] . [[2, 1]] => [1, 1]



36
37
38
 
# File 'lib/falafel.rb', line 36

def compose(lft, rgt)
  lft.flat_map { |x, y1| rgt.select { |y2, _| y1 == y2 }.map { |_, z| [x, z] } }
end

#dfa_to_min(automat) ⇒ Object 



96
97
98
99
100
101
102
103
104
105
 
# File 'lib/falafel.rb', line 96

def dfa_to_min(automat)
  d_a    = automat.delta_star[:a]
  d_b    = automat.delta_star[:b]
  states = automat.states
  starts = automat.start
  finals = automat.finals

  dfa = DFA.new { |a| a.build d_a, d_b, states: states, starts: starts, finals: finals }
  dfa.to_min
end

#nfa_to_dfa ⇒ Object 



52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
 
# File 'lib/falafel.rb', line 52

def nfa_to_dfa
  require_relative 'dfa'

  dfa = DFA.new { |a| a.build [], [], states: [], starts: @start, finals: [] }
  reachable     = []
  done_state    = []
  current_state = @start

  loop do
    @delta_star.each do |delta, relation|
      break if done_state.include? current_state

      res, rgt, lft = _new_state current_state, relation

      dfa.states << rgt unless dfa.states.include? rgt

      dfa.delta_star[delta] << [lft, rgt]

      reachable << res unless reachable.include? res

      reachable.delete res if done_state.include? res
    end

    break if reachable.empty?

    done_state << current_state unless done_state.include? current_state

    dfa.finals << current_state if (current_state & @finals).any?

    current_state = reachable.last

    reachable.pop
  end
  dfa.finals.uniq!

  _print_dfa dfa

  dfa
end

#nfa_to_reg ⇒ Object 



92
93
94
 
# File 'lib/falafel.rb', line 92

def nfa_to_reg
  RX.new { |rx| rx.build @states, @delta_star, @start, @finals }
end

#potens_set ⇒ Object 



48
49
50
 
# File 'lib/falafel.rb', line 48

def potens_set
  @state_set.each { |set| @delta_star.each { |delta, relation| puts "#{set.inspect}·#{delta}() = #{_image(set, relation).inspect}" } }
end

#power_set(states) ⇒ Object

Power set of Q



41
42
43
44
45
46
 
# File 'lib/falafel.rb', line 41

def power_set(states)
  power_set = [[]]
  states.each { |e| power_set.concat(power_set.map { |set| set + [e] }) }

  power_set
end

#pump_lemma(lang, length) ⇒ Object 



107
108
109
110
111
 
# File 'lib/falafel.rb', line 107

def pump_lemma(lang, length)
  require_relative 'pump'

  Pump.new lang: lang, length: length
end

#relation(max) ⇒ Object

Binary relation for max number



30
31
32
 
# File 'lib/falafel.rb', line 30

def relation(max)
  (1..max).flat_map { |x| (1..3).map { |y| [x, y] } }
end