A subset language of a context-free language is decidable?

Question

A subset language of a context-free language is decidable?

Asked 5 years ago

Viewed 66 times

6

If we have a context-free language L and L' is a subset of L, then L' is decidable?

2

Just to give more context to those who will answer, imagine that we have a LLC L of parentheses: every open parenthesis needs to be closed and I cannot close something that has not been opened. It means that ((()())) is valid, however ((())())) is not valid. Now imagine that I take this language and remove all words that contain (()) called L'; this means that ((())()) belongs to L, but not to L', and ((()())) belongs to both

– Jefferson Quesado

2020/10/15 at 13:32
The above comment was to illustrate that we need to deal with infinite removals of L to get L', I forgot to add this motivation in my comment

– Jefferson Quesado

2020/10/15 at 13:46

1 answer

Browser other questions tagged computer-theory formal-languages

You are not signed in. Login or sign up in order to post.

by Jefferson Quesado • **22,370** points · Answer 1 · 2020-10-15T13:44:46+00:00

Imagine we have a language U which is undecidable. Her words belong to the alphabet Σ. If U exist, so it is a sublingual of Σ*.

Let us now take the following grammar G that produces L(G):

S -> AS
S -> 
A -> el(Σ)

Where el(Σ) is a letter of Σ, any one. This language is equivalent to Σ*. Therefore, if there is a language U for that alphabet, we have to U is subset of L(G). And L(G) is a regular language, so it is also a context-free language.