The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
17 views
Let G1 be a context free grammar and G2 be a regular grammar.Is the problem L(G1) intersection L(G2) =phi decidable?
asked ago in Theory of Computation by Active (1.2k points) | 17 views

1 Answer

0 votes

as we know that intersection of regular language and cfl is cfl and cfl is closed under emptyness. so yes its DECIDABLE.

answered ago by Active (2.8k points)
0
how u got it?
0
it asks for intersection of regular and cfl = phi ?

and we know that intersection of reg and cfl is cfl. and cfl is closed under emptyness so it is decidable.


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

38,009 questions
45,506 answers
131,660 comments
48,693 users