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

Improve this question
3
  • 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 Commented Mar 30, 2014 at 7:19
  • and so for A->a B c we cant construct a dfa?? Commented Mar 30, 2014 at 7: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 Commented Mar 30, 2014 at 7:28

3 Answers 3

Reset to default
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

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

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.

Improve this answer

1 Comment

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.
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
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.