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

Asked

Viewed 66 times

6

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

computer-theory formal-languages
  • 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

  • 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

1 answer

7

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.

Browser other questions tagged computer-theory formal-languages

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