|
1 // DFAs and NFAs based on Scala's partial functions |
|
2 import scala.util.Try |
|
3 |
|
4 |
|
5 // type abbreviation for partial functions |
|
6 type :=>[A, B] = PartialFunction[A, B] |
|
7 |
|
8 |
|
9 // some states for test cases |
|
10 abstract class State |
|
11 case object Q0 extends State |
|
12 case object Q1 extends State |
|
13 case object Q2 extends State |
|
14 case object Q3 extends State |
|
15 case object Q4 extends State |
|
16 case object Q5 extends State |
|
17 case object Q6 extends State |
|
18 |
|
19 |
|
20 // class for DFAs |
|
21 case class DFA[A, C](start: A, // starting state |
|
22 delta: (A, C) :=> A, // transition |
|
23 fins: A => Boolean) { // final states |
|
24 |
|
25 // given a state and a "string", what is the next |
|
26 // state, if there is any? |
|
27 def deltas(q: A, s: List[C]) : A = s match { |
|
28 case Nil => q |
|
29 case c::cs => deltas(delta(q, c), cs) |
|
30 } |
|
31 |
|
32 // is a "string" accepted by an DFA? |
|
33 def accepts(s: List[C]) : Boolean = |
|
34 Try(fins(deltas(start, s))) getOrElse false |
|
35 |
|
36 } |
|
37 |
|
38 // DFA 1 |
|
39 val dtrans1 : (State, Char) :=> State = |
|
40 { case (Q0, 'a') => Q0 |
|
41 case (Q0, 'b') => Q1 |
|
42 } |
|
43 |
|
44 val dfa1 = DFA(Q0, dtrans1, Set[State](Q1)) |
|
45 |
|
46 dfa1.accepts("aaab".toList) // true |
|
47 dfa1.accepts("aacb".toList) // false |
|
48 |
|
49 // another DFA test |
|
50 abstract class S |
|
51 case object S0 extends S |
|
52 case object S1 extends S |
|
53 case object S2 extends S |
|
54 case object Sink extends S |
|
55 |
|
56 // transition function with a sink state |
|
57 // S0 --a--> S1 --a--> S2 |
|
58 val sigma : (S, Char) :=> S = |
|
59 { case (S0, 'a') => S1 |
|
60 case (S1, 'a') => S2 |
|
61 case _ => Sink |
|
62 } |
|
63 |
|
64 val dfa1a = DFA(S0, sigma, Set[S](S2)) |
|
65 |
|
66 dfa1a.accepts("aa".toList) //true |
|
67 dfa1a.accepts("".toList) //false |
|
68 dfa1a.accepts("ab".toList) //false |
|
69 |
|
70 |
|
71 // class for NFAs |
|
72 case class NFA[A, C](starts: Set[A], // starting states |
|
73 delta: Set[(A, C) :=> A], // transitions |
|
74 fins: A => Boolean) { // final states |
|
75 |
|
76 // given a state and a character, what is the set of next states? |
|
77 // if there is none => empty set |
|
78 def next(q: A, c: C) : Set[A] = |
|
79 delta.flatMap((d) => Try(d(q, c)).toOption) |
|
80 |
|
81 def nexts(qs: Set[A], c: C) : Set[A] = |
|
82 qs.flatMap(next(_, c)) |
|
83 |
|
84 // given some states and a string, what is the set of next states? |
|
85 def deltas(qs: Set[A], s: List[C]) : Set[A] = s match { |
|
86 case Nil => qs |
|
87 case c::cs => deltas(nexts(qs, c), cs) |
|
88 } |
|
89 |
|
90 // is a string accepted by an NFA? |
|
91 def accepts(s: List[C]) : Boolean = |
|
92 deltas(starts, s).exists(fins) |
|
93 } |
|
94 |
|
95 |
|
96 |
|
97 |
|
98 // NFA test cases |
|
99 |
|
100 // 1 |
|
101 val trans1 = Set[(State, Char) :=> State]( |
|
102 { case (Q0, 'a') => Q1 }, |
|
103 { case (Q0, _) => Q0 }, |
|
104 { case (Q1, _) => Q2 }, |
|
105 { case (Q2, _) => Q3 }, |
|
106 { case (Q3, _) => Q4 }, |
|
107 { case (Q4, 'b') => Q5 }, |
|
108 { case (Q5, 'c') => Q6 } |
|
109 ) |
|
110 |
|
111 val nfa1 = NFA(Set[State](Q0), trans1, Set[State](Q6)) |
|
112 |
|
113 nfa1.accepts("axaybzbc".toList) // true |
|
114 nfa1.accepts("aaaaxaybzbc".toList) // true |
|
115 nfa1.accepts("axaybzbd".toList) // false |
|
116 |
|
117 |
|
118 // 2 |
|
119 val trans2 = Set[(State, Char) :=> State]( |
|
120 { case (Q0, 'a') => Q0 }, |
|
121 { case (Q0, 'a') => Q1 }, |
|
122 { case (Q0, 'b') => Q2 }, |
|
123 { case (Q1, 'a') => Q1 }, |
|
124 { case (Q2, 'b') => Q2 } |
|
125 ) |
|
126 |
|
127 val nfa2 = NFA(Set[State](Q0), trans2, Set[State](Q2)) |
|
128 |
|
129 nfa2.accepts("aa".toList) // false |
|
130 nfa2.accepts("aaaaa".toList) // false |
|
131 nfa2.accepts("aaaaab".toList) // true |
|
132 nfa2.accepts("aaaaabbb".toList) // true |
|
133 nfa2.accepts("aaaaabbbaaa".toList) // false |
|
134 nfa2.accepts("ac".toList) // false |
|
135 |
|
136 // 3 |
|
137 val trans3 = Set[(State, Char) :=> State]( |
|
138 { case (Q0, _) => Q0 }, |
|
139 { case (Q0, 'a') => Q1 }, |
|
140 { case (Q0, 'b') => Q3 }, |
|
141 { case (Q1, 'b') => Q2 }, |
|
142 { case (Q2, 'c') => Q5 }, |
|
143 { case (Q3, 'c') => Q4 }, |
|
144 { case (Q4, 'd') => Q5 } |
|
145 ) |
|
146 |
|
147 val nfa3 = NFA(Set[State](Q0), trans3, Set[State](Q5)) |
|
148 |
|
149 nfa3.accepts("aaaaabc".toList) // true |
|
150 nfa3.accepts("aaaabcd".toList) // true |
|
151 nfa3.accepts("aaaaab".toList) // false |
|
152 nfa3.accepts("aaaabc".toList) // true |
|
153 nfa3.accepts("aaaaabbbaaa".toList) // false |
|
154 |
|
155 |
|
156 |
|
157 // subset, or powerset, construction |
|
158 def powerset[A, C](nfa: NFA[A, C]) : DFA[Set[A], C] = { |
|
159 DFA(nfa.starts, |
|
160 { case (qs, c) => nfa.nexts(qs, c) }, |
|
161 _.exists(nfa.fins)) |
|
162 } |
|
163 |
|
164 val dfa2 = powerset(nfa1) |
|
165 |
|
166 dfa2.accepts("axaybzbc".toList) // true |
|
167 dfa2.accepts("aaaaxaybzbc".toList) // true |
|
168 dfa2.accepts("axaybzbd".toList) // false |
|
169 |
|
170 val dfa3 = powerset(nfa2) |
|
171 |
|
172 dfa3.accepts("aa".toList) // false |
|
173 dfa3.accepts("aaaaa".toList) // false |
|
174 dfa3.accepts("aaaaab".toList) // true |
|
175 dfa3.accepts("aaaaabbb".toList) // true |
|
176 dfa3.accepts("aaaaabbbaaa".toList) // false |
|
177 dfa3.accepts("ac".toList) // false |
|
178 |
|
179 |
|
180 |
|
181 |
|
182 // epsilon NFA |
|
183 |
|
184 |
|
185 // fixpoint construction |
|
186 import scala.annotation.tailrec |
|
187 @tailrec |
|
188 def fixpT[A](f: A => A, x: A): A = { |
|
189 val fx = f(x) |
|
190 if (fx == x) x else fixpT(f, fx) |
|
191 } |
|
192 |
|
193 |
|
194 case class eNFA[A, C](starts: Set[A], // starting state |
|
195 delta: Set[(A, Option[C]) :=> A], // transition edges |
|
196 fins: A => Boolean) { // final states |
|
197 |
|
198 // epsilon transitions |
|
199 def enext(q: A) : Set[A] = |
|
200 delta.flatMap((d) => Try(d(q, None)).toOption) |
|
201 |
|
202 def enexts(qs: Set[A]) : Set[A] = |
|
203 qs ++ qs.flatMap(enext(_)) |
|
204 |
|
205 // epsilon closure |
|
206 def ecl(qs: Set[A]) : Set[A] = |
|
207 fixpT(enexts, qs) |
|
208 |
|
209 // "normal" transition |
|
210 def next(q: A, c: C) : Set[A] = |
|
211 delta.flatMap((d) => Try(d(q, Some(c))).toOption) |
|
212 |
|
213 def nexts(qs: Set[A], c: C) : Set[A] = |
|
214 qs.flatMap(next(_, c)) |
|
215 |
|
216 def deltas(qs: Set[A], s: List[C]) : Set[A] = s match { |
|
217 case Nil => ecl(qs) |
|
218 case c::cs => deltas(ecl(nexts(ecl(qs), c)), cs) |
|
219 } |
|
220 |
|
221 def accepts(s: List[C]) : Boolean = |
|
222 deltas(starts, s.toList).exists(fins) |
|
223 } |
|
224 |
|
225 |
|
226 val etrans1 = Set[(State, Option[Char]) :=> State]( |
|
227 { case (Q0, Some('a')) => Q1 }, |
|
228 { case (Q1, None) => Q0 } |
|
229 ) |
|
230 |
|
231 val enfa = eNFA(Set[State](Q0), etrans1, Set[State](Q1)) |
|
232 |
|
233 enfa.accepts("a".toList) // true |
|
234 enfa.accepts("".toList) // false |
|
235 enfa.accepts("aaaaa".toList) // true |
|
236 enfa.accepts("aaaaab".toList) // flase |
|
237 enfa.accepts("aaaaabbb".toList) // false |
|
238 enfa.accepts("aaaaabbbaaa".toList) // false |
|
239 enfa.accepts("ac".toList) // false |
|
240 |
|
241 |
|
242 |
|
243 // Regular expressions fro derivative automata |
|
244 |
|
245 abstract class Rexp |
|
246 case object ZERO extends Rexp |
|
247 case object ONE extends Rexp |
|
248 case class CHAR(c: Char) extends Rexp { |
|
249 override def toString = c.toString |
|
250 } |
|
251 case object ALL extends Rexp { |
|
252 override def toString = "." |
|
253 } |
|
254 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
|
255 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp { |
|
256 override def toString = r1.toString + " ~ " + r2.toString |
|
257 } |
|
258 case class STAR(r: Rexp) extends Rexp { |
|
259 override def toString = r.toString + "*" |
|
260 } |
|
261 case class NTIMES(r: Rexp, n: Int) extends Rexp { |
|
262 override def toString = r.toString + "{" + n.toString + "}" |
|
263 } |
|
264 case class UPNTIMES(r: Rexp, n: Int) extends Rexp |
|
265 |
|
266 |
|
267 def get_chars(r: Rexp) : Set[Char] = r match { |
|
268 case ZERO => Set() |
|
269 case ONE => Set() |
|
270 case CHAR(c) => Set(c) |
|
271 case ALT(r1, r2) => get_chars(r1) ++ get_chars(r2) |
|
272 case SEQ(r1, r2) => get_chars(r1) ++ get_chars(r2) |
|
273 case STAR(r) => get_chars(r) |
|
274 case NTIMES(r, _) => get_chars(r) |
|
275 case UPNTIMES(r, _) => get_chars(r) |
|
276 case ALL => ('a' to 'z').toSet |
|
277 } |
|
278 |
|
279 |
|
280 |
|
281 import scala.language.implicitConversions |
|
282 import scala.language.reflectiveCalls |
|
283 |
|
284 def charlist2rexp(s: List[Char]): Rexp = s match { |
|
285 case Nil => ONE |
|
286 case c::Nil => CHAR(c) |
|
287 case c::s => SEQ(CHAR(c), charlist2rexp(s)) |
|
288 } |
|
289 implicit def string2rexp(s: String): Rexp = charlist2rexp(s.toList) |
|
290 |
|
291 implicit def RexpOps (r: Rexp) = new { |
|
292 def | (s: Rexp) = ALT(r, s) |
|
293 def % = STAR(r) |
|
294 def ~ (s: Rexp) = SEQ(r, s) |
|
295 } |
|
296 |
|
297 implicit def stringOps (s: String) = new { |
|
298 def | (r: Rexp) = ALT(s, r) |
|
299 def | (r: String) = ALT(s, r) |
|
300 def % = STAR(s) |
|
301 def ~ (r: Rexp) = SEQ(s, r) |
|
302 def ~ (r: String) = SEQ(s, r) |
|
303 } |
|
304 |
|
305 def simp(r: Rexp) : Rexp = r match { |
|
306 case ALT(r1, r2) => (simp(r1), simp(r2)) match { |
|
307 case (ZERO, r2s) => r2s |
|
308 case (r1s, ZERO) => r1s |
|
309 case (r1s, r2s) => if (r1s == r2s) r1s else ALT (r1s, r2s) |
|
310 } |
|
311 case SEQ(r1, r2) => (simp(r1), simp(r2)) match { |
|
312 case (ZERO, _) => ZERO |
|
313 case (_, ZERO) => ZERO |
|
314 case (ONE, r2s) => r2s |
|
315 case (r1s, ONE) => r1s |
|
316 case (r1s, r2s) => SEQ(r1s, r2s) |
|
317 } |
|
318 case NTIMES(r, n) => if (n == 0) ONE else NTIMES(simp(r), n) |
|
319 case UPNTIMES(r, n) => if (n == 0) ONE else UPNTIMES(simp(r), n) |
|
320 case r => r |
|
321 } |
|
322 |
|
323 |
|
324 // nullable function: tests whether the regular |
|
325 // expression can recognise the empty string |
|
326 def nullable(r: Rexp) : Boolean = r match { |
|
327 case ZERO => false |
|
328 case ONE => true |
|
329 case CHAR(_) => false |
|
330 case ALL => false |
|
331 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
|
332 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
|
333 case STAR(_) => true |
|
334 case NTIMES(r, i) => if (i == 0) true else nullable(r) |
|
335 case UPNTIMES(r: Rexp, n: Int) => true |
|
336 } |
|
337 |
|
338 // derivative of a regular expression w.r.t. a character |
|
339 def der(c: Char, r: Rexp) : Rexp = r match { |
|
340 case ZERO => ZERO |
|
341 case ONE => ZERO |
|
342 case CHAR(d) => if (c == d) ONE else ZERO |
|
343 case ALL => ONE |
|
344 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
|
345 case SEQ(r1, r2) => |
|
346 if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) |
|
347 else SEQ(der(c, r1), r2) |
|
348 case STAR(r1) => SEQ(der(c, r1), STAR(r1)) |
|
349 case NTIMES(r1, i) => |
|
350 if (i == 0) ZERO else |
|
351 if (nullable(r1)) SEQ(der(c, r1), UPNTIMES(r1, i - 1)) |
|
352 else SEQ(der(c, r1), NTIMES(r1, i - 1)) |
|
353 case UPNTIMES(r1, i) => |
|
354 if (i == 0) ZERO |
|
355 else SEQ(der(c, r1), UPNTIMES(r1, i - 1)) |
|
356 } |
|
357 |
|
358 |
|
359 // partial derivative of a regular expression w.r.t. a character |
|
360 def pder(c: Char, r: Rexp) : Set[Rexp] = r match { |
|
361 case ZERO => Set() |
|
362 case ONE => Set() |
|
363 case CHAR(d) => if (c == d) Set(ONE) else Set() |
|
364 case ALL => Set(ONE) |
|
365 case ALT(r1, r2) => pder(c, r1) ++ pder(c, r2) |
|
366 case SEQ(r1, r2) => |
|
367 (for (pr1 <- pder(c, r1)) yield SEQ(pr1, r2)) ++ |
|
368 (if (nullable(r1)) pder(c, r2) else Set()) |
|
369 case STAR(r1) => |
|
370 for (pr1 <- pder(c, r1)) yield SEQ(pr1, STAR(r1)) |
|
371 case NTIMES(r1, i) => |
|
372 if (i == 0) Set() else |
|
373 if (nullable(r1)) |
|
374 for (pr1 <- pder(c, r1)) yield SEQ(pr1, UPNTIMES(r1, i - 1)) |
|
375 else |
|
376 for (pr1 <- pder(c, r1)) yield SEQ(pr1, NTIMES(r1, i - 1)) |
|
377 case UPNTIMES(r1, i) => |
|
378 if (i == 0) Set() |
|
379 else |
|
380 for (pr1 <- pder(c, r1)) yield SEQ(pr1, UPNTIMES(r1, i - 1)) |
|
381 } |
|
382 |
|
383 def ppder(c: Char, rs: Set[Rexp]) : Set[Rexp] = |
|
384 rs.flatMap(pder(c, _)) |
|
385 |
|
386 |
|
387 |
|
388 // quick-and-dirty translation of a pder automaton |
|
389 |
|
390 val r = STAR(ALL) ~ "a" ~ NTIMES(ALL, 3) ~ "bc" |
|
391 val pder_nfa = NFA[Set[Rexp], Char](Set(Set(r)), |
|
392 Set( { case (rs, c) => rs.flatMap(pder(c, _))} ), |
|
393 _.exists(nullable)) |
|
394 |
|
395 |
|
396 |
|
397 pder_nfa.accepts("axaybzbc".toList) // true |
|
398 pder_nfa.accepts("aaaaxaybzbc".toList) // true |
|
399 pder_nfa.accepts("axaybzbd".toList) // false |
|
400 |
|
401 |
|
402 |
|
403 // Derivative and Partial Derivative Automaton construction |
|
404 |
|
405 |
|
406 type DState = Rexp // state type of the derivative automaton |
|
407 type DStates = Set[Rexp] |
|
408 type Trans = (DState, Char) :=> DState // transition functions of the der/pder auto |
|
409 type MTrans = Map[(DState, Char), DState] // transition Maps |
|
410 type STrans = Set[MTrans] // set of transition Maps |
|
411 |
|
412 |
|
413 |
|
414 // Brzozoswki Derivative automaton construction ... simple |
|
415 // version, might not terminate |
|
416 |
|
417 def goto(sigma: Set[Char], delta: MTrans, qs: DStates, q: DState, c: Char) : (DStates, MTrans) = { |
|
418 val qder = simp(der(c, q)) |
|
419 qs.find(_ == qder) match { |
|
420 case Some(qexists) => (qs, delta + ((q, c) -> qexists)) |
|
421 case None => explore(sigma, delta + ((q, c) -> qder), qs + qder, qder) |
|
422 } |
|
423 } |
|
424 |
|
425 def explore(sigma: Set[Char], delta: MTrans, qs: DStates, q: DState) : (DStates, MTrans) = |
|
426 sigma.foldLeft((qs, delta)) { case ((qs, delta), c) => goto(sigma, delta, qs, q, c) } |
|
427 |
|
428 |
|
429 def mkDFA(r: Rexp) = { |
|
430 val sigma = get_chars(r) |
|
431 val (qs, delta) = explore(sigma, Map(), Set[Rexp](r), r) |
|
432 val fins = qs.filter(nullable(_)) |
|
433 val deltaf : (Rexp, Char) :=> Rexp = { case (q, c) => delta(q, c) } |
|
434 println(s"Automata size: ${qs.size}") |
|
435 DFA(r, deltaf, fins) |
|
436 } |
|
437 |
|
438 val re = "ab" | "ac" |
|
439 val d1 = mkDFA(re) |
|
440 |
|
441 d1.accepts("ab".toList) // true |
|
442 d1.accepts("ac".toList) // true |
|
443 d1.accepts("aa".toList) // false |
|
444 |
|
445 val d2 = mkDFA(r) |
|
446 |
|
447 d2.accepts("axaybzbc".toList) // true |
|
448 d2.accepts("aaaaxaybzbc".toList) // true |
|
449 d2.accepts("axaybzbd".toList) // false |
|
450 |
|
451 for (n <- (1 to 10).toList) |
|
452 mkDFA(STAR(ALL) ~ "a" ~ NTIMES(ALL, n) ~ "bc") |
|
453 |
|
454 |
|
455 // this is an example where mkDFA does not terminate |
|
456 val big_aux = STAR("a" | "b") |
|
457 val big = SEQ(big_aux, SEQ("a",SEQ("b", big_aux))) |
|
458 |
|
459 //mkDFA(big) // does not terminate |
|
460 |
|
461 |
|
462 |
|
463 // Antimirov Partial derivative automata construction ... definitely terminates |
|
464 |
|
465 |
|
466 // to transform (concrete) Maps into functions |
|
467 def toFun(m: MTrans) : Trans = |
|
468 { case (q, c) => m(q, c) } |
|
469 |
|
470 def pgoto(sigma: Set[Char], delta: STrans, qs: DStates, q: DState, c: Char) : (DStates, STrans) = { |
|
471 val qders = pder(c, q).map(simp(_)) // set of simplified partial derivatives |
|
472 qders.foldLeft((qs, delta)) { case ((qs, delta), qnew) => padd(sigma, delta, qs, q, qnew, c) } |
|
473 } |
|
474 |
|
475 def padd(sigma: Set[Char], delta: STrans, qs: DStates, |
|
476 q: DState, qnew: DState, c: Char) : (DStates, STrans) = { |
|
477 qs.find(_ == qnew) match { |
|
478 case Some(qexists) => (qs, delta + Map((q, c) -> qexists)) |
|
479 case None => pexplore(sigma, delta + Map((q, c) -> qnew), qs + qnew, qnew) |
|
480 } |
|
481 } |
|
482 |
|
483 def pexplore(sigma: Set[Char], delta: STrans, qs: DStates, q: DState) : (DStates, STrans) = |
|
484 sigma.foldLeft((qs, delta)) { case ((qs, delta), c) => pgoto(sigma, delta, qs, q, c) } |
|
485 |
|
486 def mkNFA(r: Rexp) : NFA[Rexp, Char]= { |
|
487 val sigma = get_chars(r) |
|
488 val (qs, delta) = pexplore(sigma, Set(), Set(r), r) |
|
489 val fins = qs.filter(nullable(_)) |
|
490 val deltaf = delta.map(toFun(_)) |
|
491 println(s"NFA size: ${qs.size}") |
|
492 NFA(Set(r), deltaf, fins) |
|
493 } |
|
494 |
|
495 |
|
496 // simple example from Scott's paper |
|
497 |
|
498 val n1 = mkNFA(re) // size = 4 |
|
499 |
|
500 n1.accepts("ab".toList) // true |
|
501 n1.accepts("ac".toList) // true |
|
502 n1.accepts("aa".toList) // false |
|
503 |
|
504 // example from: Partial Derivative and Position Bisimilarity |
|
505 // Automata, Eva Maia, Nelma Moreira, Rogerio Reis |
|
506 |
|
507 val r_test = STAR(("a" ~ STAR("b")) | "b") ~ "a" |
|
508 val t1 = pder('a', r_test).map(simp(_)) |
|
509 val t2 = pder('b', r_test).map(simp(_)) |
|
510 |
|
511 mkNFA(r_test) // size = 3 |
|
512 |
|
513 |
|
514 // simple example involving double star |
|
515 // with depth-first search causes catastrophic backtracing |
|
516 |
|
517 val n2 = mkNFA(STAR(STAR("a")) ~ "b") // size 3 |
|
518 |
|
519 n2.accepts("aaaaaab".toList) // true |
|
520 n2.accepts("aaaaaa".toList) // false |
|
521 n2.accepts(("a" * 100).toList) // false |
|
522 |
|
523 val r1 = STAR(ALL) ~ "a" ~ NTIMES(ALL, 1) ~ "bc" |
|
524 mkNFA(r1) // size = 5 |
|
525 |
|
526 val n3 = mkNFA(r) // size = 7 |
|
527 |
|
528 n3.accepts("axaybzbc".toList) // true |
|
529 n3.accepts("aaaaxaybzbc".toList) // true |
|
530 n3.accepts("axaybzbd".toList) // false |
|
531 |
|
532 for (n <- (1 to 100).toList) |
|
533 mkNFA(STAR(ALL) ~ "a" ~ NTIMES(ALL, n) ~ "bc") |