DPLL algorithm - regular languages [closed]
up vote
-4
down vote
favorite
So I got this exercise from uni:
The DPLL algorithm does something boring (case-split) when it
can cannot do anything clever, such as remove tautologies, propagate unit
clauses, or remove clauses with pure literals. But can we leave the detection
whether we can do something clever to a finite automaton, in any of the cases?
Technically, this boils down to answering the following questions:
(a) Is the language of CNFs that contain a tautological clause regular?
(b) Is the language of CNFs that contain a pure literal regular?
(c) Is the language of CNFs that contain a unit clause regular?
I've been looking all over the lectures and youtube tuts but can't understand any of this. Can anyone help me or point me to a website where I can learn?
logic algorithms regular-language
asked Nov 21 at 22:01
Bogdan Domide
1
closed as off-topic by Brian Borchers, amWhy, José Carlos Santos, Leucippus, Cesareo Nov 22 at 1:43
This question appears to be off-topic. The users who voted to close gave these specific reasons:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – amWhy, Leucippus, Cesareo
- "This question is not about mathematics, within the scope defined in the help center." – Brian Borchers, José Carlos Santos
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
up vote
-4
down vote
favorite
So I got this exercise from uni:
The DPLL algorithm does something boring (case-split) when it
can cannot do anything clever, such as remove tautologies, propagate unit
clauses, or remove clauses with pure literals. But can we leave the detection
whether we can do something clever to a finite automaton, in any of the cases?
Technically, this boils down to answering the following questions:
(a) Is the language of CNFs that contain a tautological clause regular?
(b) Is the language of CNFs that contain a pure literal regular?
(c) Is the language of CNFs that contain a unit clause regular?
I've been looking all over the lectures and youtube tuts but can't understand any of this. Can anyone help me or point me to a website where I can learn?
logic algorithms regular-language
asked Nov 21 at 22:01
Bogdan Domide
1
closed as off-topic by Brian Borchers, amWhy, José Carlos Santos, Leucippus, Cesareo Nov 22 at 1:43
This question appears to be off-topic. The users who voted to close gave these specific reasons:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – amWhy, Leucippus, Cesareo
- "This question is not about mathematics, within the scope defined in the help center." – Brian Borchers, José Carlos Santos
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
up vote
-4
down vote
favorite
up vote
-4
down vote
favorite
So I got this exercise from uni:
The DPLL algorithm does something boring (case-split) when it
can cannot do anything clever, such as remove tautologies, propagate unit
clauses, or remove clauses with pure literals. But can we leave the detection
whether we can do something clever to a finite automaton, in any of the cases?
Technically, this boils down to answering the following questions:
(a) Is the language of CNFs that contain a tautological clause regular?
(b) Is the language of CNFs that contain a pure literal regular?
(c) Is the language of CNFs that contain a unit clause regular?
I've been looking all over the lectures and youtube tuts but can't understand any of this. Can anyone help me or point me to a website where I can learn?
logic algorithms regular-language
asked Nov 21 at 22:01
Bogdan Domide
1
So I got this exercise from uni:
The DPLL algorithm does something boring (case-split) when it
can cannot do anything clever, such as remove tautologies, propagate unit
clauses, or remove clauses with pure literals. But can we leave the detection
whether we can do something clever to a finite automaton, in any of the cases?
Technically, this boils down to answering the following questions:
(a) Is the language of CNFs that contain a tautological clause regular?
(b) Is the language of CNFs that contain a pure literal regular?
(c) Is the language of CNFs that contain a unit clause regular?
I've been looking all over the lectures and youtube tuts but can't understand any of this. Can anyone help me or point me to a website where I can learn?
logic algorithms regular-language
logic algorithms regular-language
asked Nov 21 at 22:01
Bogdan Domide
1
asked Nov 21 at 22:01
Bogdan Domide
1
asked Nov 21 at 22:01
Bogdan Domide
1
asked Nov 21 at 22:01
Bogdan Domide
1
asked Nov 21 at 22:01
Bogdan Domide
1
1
closed as off-topic by Brian Borchers, amWhy, José Carlos Santos, Leucippus, Cesareo Nov 22 at 1:43
This question appears to be off-topic. The users who voted to close gave these specific reasons:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – amWhy, Leucippus, Cesareo
- "This question is not about mathematics, within the scope defined in the help center." – Brian Borchers, José Carlos Santos
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by Brian Borchers, amWhy, José Carlos Santos, Leucippus, Cesareo Nov 22 at 1:43
This question appears to be off-topic. The users who voted to close gave these specific reasons:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – amWhy, Leucippus, Cesareo
- "This question is not about mathematics, within the scope defined in the help center." – Brian Borchers, José Carlos Santos
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
