# Given regular grammars (each is either left or right linear), does exist word/string so it can be derived from all regular grammars?

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}?

• Hint: You need to decide whether the intersection is empty. – Raphael Jul 10 '17 at 23:35
• And how do I do this exactly? – Farewell Stack Exchange Jul 10 '17 at 23:47
• @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/… – rici Jul 11 '17 at 0:05
• And what is both the time and space complexity price to do this? – Farewell Stack Exchange Jul 11 '17 at 0:55
• @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. – D.W. Jul 11 '17 at 6:09

• 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). – Yuval Filmus Jul 11 '17 at 10:13