0
$\begingroup$

Given regular grammars (each is either left or right linear), does exist word/string so it can be derived from all regular grammars, i.e. a word/string that can be derived from each regular grammar.

Suppose that S1, ... , Sn are regular grammars. Then is the following statement is true:

∃w: S1→w ∧ ... ∧ Sn→w ?

In other words:

∃w∀i: 1≤i≤n→(Si→w) ?

Does exist polynomial algorithm (both in time and space) that can find the answer to this question quickly?

EDIT: The language of each given regular grammar is finite and 'w' is a word of length m, where m is natural number given as input to the algorithm.

Also the alphabet of each regular grammar is Σ={0,1} and thus |Σ|=2.

In other words, does exist word of length m that can be derived from each regular grammar, where the language of each regular grammar is finite and alphabet of each regular grammar is {0,1}?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Hint: You need to decide whether the intersection is empty. $\endgroup$
    – Raphael
    Commented Jul 10, 2017 at 23:35
  • $\begingroup$ And how do I do this exactly? $\endgroup$
    – Farewell Stack Exchange
    Commented Jul 10, 2017 at 23:47
  • $\begingroup$ @erez: One simple way would be to construct the intersection automaton and see if it has any accessible accepting states. Also see cstheory.stackexchange.com/questions/29142/… $\endgroup$
    – rici
    Commented Jul 11, 2017 at 0:05
  • $\begingroup$ And what is both the time and space complexity price to do this? $\endgroup$
    – Farewell Stack Exchange
    Commented Jul 11, 2017 at 0:55
  • 4
    $\begingroup$ @ErezZrihen, why don't you study the method, see what you can work out, and if you're still stuck, edit the question to show what approaches you've tried and why you've rejected them or where you got stuck in analyzing them? It's your exercise, so you should be prepared to do some work to figure this out. $\endgroup$
    – D.W. ♦
    Commented Jul 11, 2017 at 6:09

1 Answer 1

Reset to default
2
$\begingroup$

Your problem is PSPACE-complete. Indeed, the easier problem of DFA intersection is already PSPACE-complete, see for example Descriptional and computational complexity of finite automata—A survey by Holzer and Kutrib. For comparable results from the point of view of exponential time algorithms, see Problems on Finite automata and the exponential time hypothesis by Fernau and Krebs.

It is well-known that regular grammars are essentially equivalent in power to NFAs (even considering description complexity), and for this reason your problem is essentially equivalent to the NFA intersection problem, in which you are given a collection of NFAs and have to decide whether the intersection of languages accepted by them is empty — this is the problem considered in the papers above.

The same problem for regular expressions is also PSPACE-complete, see for example Complexity of decision problems for simple regular expressions by Martens, Neven and Schwentick, which considers restricted cases of the problem.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I have edited my question: Now it is known that the language of each regular grammar is finite and 'm' is natural number given as input to the algorithm and there is need to find a word of length m that can be derived from each regular grammar. Also the alphabet of each regular grammar is {0,1}. $\endgroup$
    – Farewell Stack Exchange
    Commented Jul 11, 2017 at 10:03
  • $\begingroup$ The problem remains NP-hard at the very least, by a simple reduction from SAT. The exact complexity depends on how you encode $m$ (in binary or in unary). $\endgroup$
    – Yuval Filmus
    Commented Jul 11, 2017 at 10:13
  • $\begingroup$ Can you show how the reduction from SAT to this problem is done exactly? $\endgroup$
    – Farewell Stack Exchange
    Commented Jul 11, 2017 at 11:11
  • 1
    $\begingroup$ It's a nice exercise. If you're interested, please ask a new question. Changing the question invalidates existing answers, which goes against the spirit of this forum. $\endgroup$
    – Yuval Filmus
    Commented Jul 11, 2017 at 11:12
  • $\begingroup$ You are right, I will ask a new question then. $\endgroup$
    – Farewell Stack Exchange
    Commented Jul 11, 2017 at 11:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.