# Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

2,455 questions
Filter by
Sorted by
Tagged with
80 views

### context-free language : if yx belongs to cfl then xy is also cfl [duplicate]

I faced a problem. What is the proof to say that if yx is in a Context-Free Language we can say that xy is also in a context-free language. C is a Context-Free Language. I think we can use the PDA ...
64 views

### Design a CFG that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }

I am trying to design a context-free grammar that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }. This is really confusing me, I'm having trouble with ...
35 views

### Designing CFG that accepts $b^m a^n$ ($m ≤ n$)

I am trying to design a CFG that generates the language $\{a^k b^m a^n a^k \mid m \leq n\}$. However, I am having trouble with the $b^m a^n$ where $m \leq n$. How do I solve this?
52 views

### Is the empty string and some words of even length are elements of this set?

$L = \{w \in \{a,b\}^*| \text{the first, the middle, and the last characters of$w$are identical}\}$. I have my answers, but I need confirmation: Is the empty string $\epsilon \in L$? Yes. Reason: ...
119 views

### When our two-state PDA constructed from CFG is non-deterministic PDA?

We can always convert our GNF-CFG/CNF-CFG to a two-state PDA but i'm wondering when our PDA is non-deterministic? i'm sure we can not make DPDA for non-Deterministic-CFL , and i suspect that same rule ...
28 views

### Shortest unambiguous representation of a graph over an alphabet

I just started reading a book on theoretical computer science and here are a couple of beginner questions about graphs, which I am struggling to answer: Given the graph with the matrix ...
101 views

### Difference between assignment, binding, and substitution?

I am trying to understand the difference of assignment, binding, and substitution. I know the three things are related, but to me it's not exactly clear what word refers to what. Example, illustration,...
34 views

### How to find the language and create Push down automaton if the A is continuously looping ? and will PDA accept L produced without A

Let us consider the following Context-Free Grammar G = ({S,A,B,C,D},{a, b}, S, P) with production rules P: S → SSA | Bb A → BSA B → A | Cb C → AD | Cb | ɛ D → a | b | ɛ Let L be the language ...
53 views

### PDA with more than one initial state

I'm wondering if PDAs with more than one initial states are also accepting context free languages. If found that question on this site about NFAs and would like to know if this answer is also valid ...
35 views

### Proof for palindrome grammar by induction

I can't seem to find a solution to the following question. Given the following grammar for palindromes: $$G_{pal}=\{\{a,\dots,z\},\{P\},P,R\},$$ with $R$ consisting of the rules ...
215 views

20 views

### Are DPDAs accepting on final state equivalent to DPDAs accepting on empty stack equivalent? [duplicate]

Say I have a string x that is accepted by some DPDA P that accepts empty stack. Intuitively it's seems impossible for P to accept any string x.y for any y != epsilon. The below DPDA accepts on final ...
28 views

9 views

### Writing a Grammar to a Language [duplicate]

is there a general method or approach to writing grammars to a language? I do not want to describe the language I have to write a grammar to as I do not want a specific answer. I am looking for ...
65 views

### Is the language of palindromes context-free?

Is the language $\{ w=w^R \mid w \in \{0,1\}^* \}$ a context-free language? I am confused in deciding whether the language is context-free or not, that is one of my problems, I do a pumping lemma ...
61 views

### Languages such that DFA requires $\Omega(c^k)$ states but NFA needs only $O(k)$ states?

Given an alphabet $\Sigma$, let $c=|\Sigma|$. Can a set of languages $\{L_k\}$ be created, such that any DFA for $L_k$ has $\Omega(c^k)$ states and a NFA for $L_k$ exists with $O(k)$ states? I'm ...
30 views

### Understanding Subset construction in following example

In going through the paper, Synthesizing Runtime Enforcer of Safety Properties Under Burst Error, https://link.springer.com/chapter/10.1007/978-3-319-40648-0_6, where the example automata considered ...
72 views

### The total length of input to a pushdown automata which accepts by empty stack is an upper bound on the number states and stack symbols

I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" (3rd Edition) by Jeffrey Ullman ,John Hopcroft, Rajeev Motwani, where I came across few statements ...
Let $L_1=\{Q,\Sigma,q_0,\delta,Q\}$ be a DFA that accepts a language $L$ and where all the states are also final states. If we want a DFA that accepts the complement of $L$, we swap its accepting ...
I was reading up on DFA's and their accepted languages when I stumbled across this: Let a DFA $M$ accept the language $L⊆Σ^∗$, DFA $M'$ accepts $P(L)=$ {$w∈Σ^∗|wy∈L$ for some $y∈Σ^∗$}. Since any $wy$...