edited by
657 views
4 votes
4 votes

Consider the languages $A$ and $B$, each over the alphabet set $\left \{ a,b \right \}$.

Here,  $B=\{ w \mid w$ contains some $x \in A$ as a sub-string $\}.$

Which of the following is TRUE about $A$ and $B$?

  1. If $A$ is regular, then $B$ is regular.
  2. If $A$ is recursive, then $B$ is recursive.
  3. If $A$ is context-free, then $B$ is context-free.
  1.    II only
  2.    II and III
  3.    I and III only
  4.    I, II and III
edited by

1 Answer

Best answer
10 votes
10 votes

All are TRUE.

I. If A is regular, then B is regular: Given A is regular, that means A can be written as a regular expression. Say, it's regular expression is e. Then the regular expression for B will be: (a+b)*e(a+b)*. Since we have a regular expression for B, this implies that B is also regular.

II. If A is recursive, then B is recursive: Given A is recursive this means that there exists a TM which given a string as input can tell whether it belongs to A or not. Lets call it TM_A. Now, using this we can create a TM which can be used for telling if a string belongs to B or not(calling it TM_B). This will prove that B is also recursive.

How to create such a TM_B?

When we have an input string for TM_B, take every possible substring of it and given it to TM_A, if any of the substring is accepted by TM_A, then the original string belongs to B. Otherwise if none of the substring is accepted by TM_A, that means that the original input string does not belong to B. Every string will be of finite length, that means that there will be a finite number of substrings to check. So, we have a TM for B, which always tells if a string is in B or not. Hence, B is also recursive.

III. If A is context-free, then B is context-free: A is context free then there will be a CFG representing it. Let's say its starting symbol is S. Now we can create another CFG with starting symbol S' 

S' -> ASA

A -> aA | bA | e

Here S is the starting symbol of A's CFG. This will produce all the strings that have some string of A as substring.

There is a CFG for B, therefore B is context free.

ALL ARE TRUE!!!

selected by
Answer:

Related questions