2
$\begingroup$

CFL = context-free-language

I would like to know does the concatenation of one CFL and one non-CFL does it necessarily give a non-CFL.

I am trying to solve the following: enter image description here

I know that CFLs are closed under concatenation.

And my approach to solve the problem is to let

L = L1.L2 where L1 = a, since L is CFL and L1 is also CFL then L2 must be CFL, however I am not sure if my approach is right!

$\endgroup$

3 Answers 3

2
$\begingroup$

The concatenation of $A^*$ with any language $L$ containing the empty word is equal to $A^*$. In particular, you can take for $L$ a non context-free language or even a non-recursive one.

Now, for your other question, $f(L) = a^{-1}L$, the left quotient of $L$ by $a$. Now, context-free languages are closed under left quotient by a regular language.

$\endgroup$
1
$\begingroup$

You know CFGs are closed with respect to substitutions and intersections with regular languages. Substitute $a \mapsto \{a, A\}$ (for each symbol $a$ invent an "uppercase" variant), intersect with the regular language of one "uppercase" symbol followed by any sequence of lower case symbols, and finally replace all uppercase (i.e., just the first here) with nothing.

$\endgroup$
0
$\begingroup$

With the help of J.-E. Pin answer I think I have found another way to solve my problem.

From An introduction to Formal Languages and Automata (fifth edition), we have a theorem.

Theorem: For every CFL L with lambda not in L, there exists a context free grammar G in Griebach Normal Form such that L = L(G)

Now let G = (V,T,S,P) be the grammar in Griebach Normal Form,
where V is set of variables
where T is set of terminals
where S is the start state
where P is set of productions

we have one or more productions in P of the form:
(all the productions that start from S)
S $\to$ aX, where a is a terminal and X $\in$ ${T^*}$

Now make S' exactly the same as S but replace the character symbol with lambda, and S' the new start state, which are production P'.

Add S' and P' to G making G'

Thus G' = (V$\cup$S',T,S', P$\cup$P') will accept the set of string obtained by dropping the first symbol.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .