Register

UGC NET CSE | June 2012 | Part 3 | Question: 16

• recategorized by
3,245 views
1 votes
1 votes

Given the following statements:

  1. The power of deterministic finite state machine and non- deterministic finite state machine are same.
  2. The power of deterministic pushdown automaton and non- deterministic pushdown automaton are same.

Which of the above is the correct statement(s)?

  1. Both I and II
  2. Only I
  3. Only II
  4. Neither I nor II
• recategorized by
User Avatar

2 Answers

1 votes
1 votes
ALL Finite Automata have same expressive power

Determistic CFL(DCFL) is a proper  subset of CFL

so DPDA < NPDA

So, B is Correct
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

2 votes
2 votes
2 answers
1
go_editor asked Jul 7, 2016
4,993 views
UGC NET CSE | June 2012 | Part 3 | Question: 52
Match the following : ... $\text{(i)-(c), (ii)-(b), (iii)-(d), (iv)-(a)}$
Match the following :$\begin{array} {clcl} \text{(i)}& \text{Regular grammer} & \text{(a)} & \text{Pushdown automaton} \\ \text{(ii)}& \text{Context free grammer} & \tex...
User Avatar
3 votes
3 votes
1 answer
2
go_editor asked Jul 7, 2016
4,374 views
UGC NET CSE | June 2012 | Part 3 | Question: 43
The regular expression for the following DFA ab*(b+aa*b)* a*b(b+aa*b)* a*b(b*+aa*b) a*b(b+aa*b)*
The regular expression for the following DFAab*(b+aa*b)*a*b(b+aa*b)*a*b(b*+aa*b)a*b(b+aa*b)*
User Avatar
1 votes
1 votes
1 answer
4
go_editor asked Jul 7, 2016
4,015 views
UGC NET CSE | June 2012 | Part 3 | Question: 35
Consider the regular expression (a+b)(a+b) ..... (a+b) (n-times). The minimum number of states in finite automaton that recognizes the language represented by this regular expression contains n states n+1 states n+2 states 2$^n$ states
Consider the regular expression (a+b)(a+b) ..... (a+b) (n-times). The minimum number of states in finite automaton that recognizes the language represented by this regula...
User Avatar
Link Copied!