The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
32 views

asked in Theory of Computation by Active (3.6k points) | 32 views

1 Answer

+1 vote

1) Given a regular language L, the minimal DFA accepting L has always exactly as many states as any minimal size NFA accepting it.

 this statement is false by counter example.

 L= set of all strings whose 2nd bit from right end is 1

for this Language NFA can be constructed by 3 states but minimal  DFA should be contain 4 states

2) If A is a DFA for a language L, and A has two states q≠p such that for some non-empty word w it holds that δ(q,w) = δ(p,w) and δ(p,w) is an accepting state then A is not minimal.

this statement  is true because δ(q,w) = δ(p,w) and q≠p means q and p are equal states, in Minimal DFA equal states are not allowed therefore A is not Minimal DFA note that two states are equal iff both are either final states or non-final states only, here δ(p,w) is an accepting state but didn't mention either p or q is final states therefore i assumed both are either final states or non-final states

3) An NFA for a language L, can be transformed into a minimal DFA for L by first carrying out the subset construction then deleting all inaccessible states.

this statement is false why because by the above mentioned approach we can get DFA but we can not assure it is Minimal.

4) Given statement is false by giving counter example

Consider a DFA with unreachable state therefore it can't be minimal

answered by Boss (31.3k points)
edited by

Related questions

0 votes
1 answer
1
0 votes
1 answer
2
asked Oct 3 in Theory of Computation by Mudita (49 points) | 25 views
0 votes
1 answer
3


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,851 questions
47,514 answers
145,843 comments
62,274 users