2

How to convert a Context Free Grammar to a DFA? This is easy if we have transitions like A->a B. But when we have the transitions as A->a B c. Then how should we represent it as a DFA

bulbasaur
  • 49
  • 1
  • 1
  • 6
  • 1
    You can't always convert CFG into DFA, But yes If it is left-linear or right liner then you can. In this case this answer can be helpful [Left-Linear and Right-Linear Grammars](http://stackoverflow.com/questions/13816439/left-linear-and-right-linear-grammars/13945932#13945932) – Grijesh Chauhan Mar 30 '14 at 07:19
  • and so for A->a B c we cant construct a dfa?? – bulbasaur Mar 30 '14 at 07:21
  • See correct way it first convert a Grammar into Left-liner or right-liner then draw DFAs. If it is not possible to convert a CFG into left-linear ( right-liner) then actually grammar generates CFL that is super-set of regular language and DFA for CFL is not possible. `A -> a B c` Only a single production rule (not a grammar) so your queston doesn't make sense – Grijesh Chauhan Mar 30 '14 at 07:28

3 Answers3

2

There is no general procedure to convert an arbitrary CFG into a DFA. For example, consider this CFG:

S → aSb | ε

This grammar is for the language { anbn | n ≥ 0 }, which is a canonical nonregular language. Since we can only build DFAs for regular languages, there’s no way to build a DFA with the same language as this CFG

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
0

First, you should convert your language to CNF (Chomskey Normal Form). Then steps for conversion are as such:

  1. Convert it to left/right grammar is called a regular grammar.

  2. Convert the Regular Grammar into Finite Automata The transitions for automata are obtained as follows For every production A -> aB make δ(A, a) = B that is make an are labeled ‘a’ from A to B. For every production A -> a make δ(A, a) = final state. For every production A -> ϵ, make δ(A, ϵ) = A and A will be final state.

River
  • 8,585
  • 14
  • 54
  • 67
e nahang
  • 3
  • 1
  • 7
  • This procedure will not always work - it may fail because the CFG is for a nonregular language, or because the conversion to CNF produces a non-left-linear or non-right-linear grammar. – templatetypedef Jun 26 '21 at 14:48
0
  • No. For these Grammar no DFA can form.
  • why?
  • because it requires memory. Memory of occurence of a.
  • Yes . it is CFL (context free Language).
  • We can design a PDA (Push down automata). Here , memory ( STACK is use ). for PUSH a and POP b
Jaykumar
  • 137
  • 2
  • 12