# Questions tagged [context-free]

Questions about the set of languages (equivalently) described by context-free grammars or accepted by (non-deterministic) pushdown automata.

1,309 questions
Filter by
Sorted by
Tagged with
61 views

39 views

### GATE CSE 2018, Which of the following languages are context-free?

A] {ambncpdq | m+p = n+q, where m, n, p, q >=0} B] {ambncpdq | m = n and p = q, where m, n, p, q >=0} C] {ambncpdq | m = n = p and p not= q, where m, n, p, q >=0} D] {ambncpdq | mn = p+q, ...
28 views

### PDA kleene star construction

I know how to prove that CFL are closed under kleene star operation using CFG. I can't find online or in class notes a proof using PDA. I would appreciate description of the basic idea (not formal).
25 views

23 views

86 views

### Is every linear language in NL?

I wonder if all the linear languages are in NL? I was thinking that we can take an input-language $L$ and convert it to linear normal form. If this is not possible, the machine rejects. If the ...
26 views

### Is the language of rectangular matrices in MATLAB-style syntax context free?

Consider the language $L$ of rectangular matrices written down as a comma separated list of integers where each list represents a row of the matrix and rows are separated by a semicolon. There may be ...