Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

250 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
0
votes
0answers
418 views

Decidability of intersection of two languages of same type

Given two context-sensitive languages, $L_1$ and $L_2$ is the problem of "whether $L_1 \cap L_2$ also belongs to CSL" decidable? I have the same question for the case when $L_1$ and $L_2$ belongs to ...
0
votes
0answers
85 views

Show that this language is not regular by Pumping Lemma

Over the alphabet $\Sigma=\{a,b\}$, we define $$L=\{a^pb^m: p\text{ is prime }, m>0\}+\{a^r:r\geq 0\}.$$ I must show that this laguage is not regular using the pumping lemma. I guess I should ...
0
votes
0answers
51 views

Is the set of TMs whose language reduces to a fixed CFL also CFL?

L = { < M > | M is a TM and L(M) <= { $0^n 1^{2n}$} } Here <= means polynomially reducible to Is L CFL? If L(M) can be polynomially reduced to a CFL then L(M) should also be CFL as if "A" ...
0
votes
0answers
81 views

Empty words in regular languages

Let $L_1,L_2$ be any $\Sigma$-Languages, with $l_1\in L_1, l_2\in L_2$ If I have a regular Language $L(l_1(l_2l_1)^*l_2)$ would the word $\omega=l_2$ be recognized? I'm confused because if $\epsilon \...
0
votes
0answers
35 views

Find any kind of grammar for the language

Find any kind of grammar for the language L = {w ∈ Σ* | in w there are twice as many a's than b's} and reason its correctness. Where ...
0
votes
0answers
201 views

How to show that a language is strictly context sensitive

During a class, we was asked how to prove that a language L is strictly context-sensitive. In particular, we have to prove that $L = \{a^nb^nc^n \mid n > 0\}$ Could you help me to find the ...
0
votes
0answers
158 views

Why don't we use $ as end marker for input in PDA?

I am reading Theory of Computation by Peter Linz. The transitions for PDA uses $\epsilon$ as end marker for input string. For example if the final state is $q_1$ then the transition is written like $\...
0
votes
0answers
17 views

Let $L_1$ be a DCFL and $L_2$ be recursive language. Is $L_1 \cap L_2$ a DCFL?

Let $L_1$ be a DCFL and $L_2$ be recursive language. Is $L_1\cap L_2$ a DCFL? According to me the intersection should be a Recursive language. However the answer given is DCFL. Can anyone confirm?
0
votes
0answers
92 views

Does this grammar generate regular language?

$S \rightarrow AB$ $A \rightarrow aA \mid bA \mid \epsilon$ $B \rightarrow aBb \mid \epsilon$ Does this grammar generate regular language? According to me this grammar generates language of the ...
0
votes
0answers
24 views

Operation on languages results in CFL

For every two languages $L_{1}$ and $L_{2}$ over the alphabet $\{ a,b,c,d \}$, we define the language $$L_{1} \operatorname{op} L_{2} = \{ \alpha\beta \mid \text{$\alpha \in L_{1}$ and $\beta \in L_{...
0
votes
0answers
49 views

Interpreting the way we choose partitions in the pumping lemma for CFLs

This question is referring to the Pumping Lemma for CFLs, namely: If $L$ is a CFL, there is a pumping length $p$ such that any string $z \in L$ of length $\geq p$ can be written as $z = uxwyz$, ...
0
votes
0answers
96 views

Doubt regarding Chomsky hierarchy

I know that intersection of CFL and regular language is CFL and hence CFL is closed if one of the languages is regular. One of the most common examples to show this is regular language being $p^*q^*$ ...
0
votes
1answer
414 views

How to define a language for an independent set problem of a graph?

Let a graph $G=(V,E)$ have an independent set $I\subseteq V$ with $\{u,v\}\notin E$ for all $u,v \in I$ and $k \in \mathbb{Z}_{>0}$ where $|I|=k$. How can I define the language $L_{P_{Independent ...
0
votes
0answers
150 views

Is this grammar in Chomsky Normal Form?

This was the initial CFG (starting symbol is I): I → aAB A → BAb | ε | B B → a | b | CD C → ba D → DD And this its CNF: ...
0
votes
0answers
341 views

CFL Intersection with Regular Language prove

how can i prove the following statement : 1- $L_1\subseteq\Sigma^*$ is CFL and $L_2\subseteq\Sigma^*$ is regular Language, then $L_1$\ $L_2$ is CFL . so i want to know what is the method to prove it ...
0
votes
0answers
113 views

Pumping Lemma - B = {0^n,1^n | n>=0}

Question : Are my justifications correct? Im very confused and im not sure im getting this correctly. Pumping Lemma - $B = {0^n1^n | n >=0}$ Prove $B$ is not regular : Suppose $S = 0^p1^p$ ...
0
votes
0answers
1k views

Difference between LR parsing and Shift-Reduce parsing?

I'm learning natural language processing and I can't understand the difference between Shift-Reduce parser and LR parser. As I've understood from Wikipedia, shift-reduce is just a name of a class of ...
0
votes
0answers
31 views

CFG notation meaning in making LL parse table

I have problem of interpreting Context-free grammar notation in making LL(1) parse table. To make LL(1) parse table. Two rules are shown below: If A -> α is a production choice, and there is a ...
0
votes
0answers
538 views

Show that an instance of PCP or MPCP has no solutions

I'm studying the Post Correspondence Problem (PCP) and understand the concept, although I have problems with proving how to show that an instance of a PCP or modified PCP has no solutions. For ...
0
votes
0answers
69 views

How to see if P is decidable semi-decidable, undecidable?

I've been trying to figure out a practice exam question, about if a given $P$. $P$ is the characteristics of recursive enumerable set given as: $$P(A) = \begin{cases} ⊤ &if &|A| ≤ 100 \\ ...
0
votes
0answers
60 views

Pumping Lemma to prove that L is not context free

I have the language and I want to prove that is not context-free. So I started like this: is variable. Choose w = Case 1: vxy has no c. Choose i = 2 has more a than c or more b than c. Case 2: ...
0
votes
0answers
85 views

Growing context-sensitive grammars with context-free rules

Has anyone ever considered the class of languages $X$ generated by growing context-sensitive productions which are described by context-free rules? In particular, I wonder if there is a NP-complete ...
0
votes
0answers
68 views

How to prove that the language of words ucv with as many a's in u as b's in v is irregular?

I'm trying to prove that: $L=\{w\in\{a,b,c\}^*\Big|\#_a(u)=\#_b(v),\ \ w=ucv,\ \ \ u,v\in\{a,b\}^*\}$ is irregular, so I'm trying to use the Pumping Lemma. This is what I tried so far: $w=a^ncb^n$...
0
votes
0answers
621 views

Describe the language generated by a given context free grammar

I had an exercise: Describe the language generated by the following given context free grammar and prove it by induction. $$\begin{align} S &\to SA \mid \epsilon \\ A &\to aS \mid bA \...
0
votes
0answers
76 views

Linear time parsing from star of context free language

I was wondering if there are cases in which the star closure of a language can make the resulting language easier to parse. In particular, if I have this grammar: ...
0
votes
0answers
86 views

Rules language / DSL expressivity measure

Languages to express domain rules are quite diverse from very simple and inexpressive to Turing-complete programming languages. If we consider developing some DSL (domain-specific language), is there ...
0
votes
0answers
358 views

What is the limit for Turing machines with 2 states and 3 symbols that halt?

I read here that a proof has been offered that a Turing Machine with 2 states and 3 symbols can be universal (in that it is capable of arbitrary finite computations). Even if this proof is accepted, ...
0
votes
0answers
178 views

Union, Intersection, Difference, etc. of different types of languages

I am preparing for a competitive exam (GATE) in which questions are asked in Automata about operations among different types of languages. For example, If $L_1$ is recursive & $L_2$ is ...
0
votes
0answers
70 views

Designing CFG for sequences of words of which two arbitrary ones are reversals

Let $L$ = {$x_1\#x_2\#...\#x_k$ : $k\;\ge\;1$, each $x_i\;\in\;\{0,1\}^*$ and $\exists i,j$ such that $i < j$ and $x_i$ = $x^R_J$}. For example, $001001\#0010\#100100\#00001$ is in $L$ because $...
0
votes
0answers
123 views

Making a regular grammar for this language

I'm trying to make a regular grammar for this language: Where the alphabet is $ \Sigma $ = $\{a,b,c\}$ It seemed like it would go well with a right-linear grammar. This may be disastrously wrong, ...
0
votes
1answer
121 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 ...
0
votes
2answers
730 views

turing machine for the language L ={w#w' where w<w'}

I'm blocked with a question for a long time. L ={X=w#w' where w < w' and w,w' in {0,1}* } So i'm trying to find : 1-a deterministric turing maching for the language L. 2-a non deterministic for ...
-1
votes
2answers
58 views

Context-free grammar for $a^{2n} b^{2n}$

I have just started learning formal languages and here is a question I am facing a little hurdle: Construct a context-free grammar for $\{ a^{2n}b^{2n} \mid n \ge 0 \}$. This was what I got at first....
-1
votes
1answer
35 views

Prove that the class of regular languages is closed under the Kleene + operation. That is, show that if L is regular, then so is $L^{+}$

This is my attempt at a proof: Let $E$ be a $REGEX$ accepting $L$. We claim the $REGEX$ $E^{'} = E^{+}$ accepts L. i.e. $L(E^{+}) = (L(E))^{+}$ $L^{+}$ is regular since there is a $REGEX$ $E^{+}$ ...
-1
votes
1answer
151 views

Turing Machine construction of M=wwRw form

Construct a Turing machine for M = {wvw| v, w ∈ {a, b}*, reversal(v) = w}. I tried to imagine that I will have to divide the string into 3 equal parts and check if ...
-1
votes
2answers
134 views

CFG for language of words with odd many $a$ and exactly two $c$

I am trying to construct a context-free grammar for the language $$ L = \{ w \in \{a,b,c\} \mid w \text{ contains an odd amount of } a \text{ and there are exactly two } c \}. $$ I am currently stuck ...
-1
votes
1answer
51 views

Set-theoretic difference of two languages in CFL - REG

Let $L_1,L_2\in$ CFL $-$ REG, with $L_1\subset L_2$. Which of the following always holds? $L_1-L_2\in$ CFL $-$ REG and $L_1-L_2\in$ REG. $L_1-L_2\in$ REG and $L_2-L_1\in$ CFL $-$ REG. $L_1-L_2\in$ ...
-1
votes
1answer
86 views

Using the pumping theorem to show that this language is not context-free

Let $\sigma = \{a,b,c\}$ and let $L = \{s | s = a^jb^jc^k\}$ where $k=i\cdot j$ and $i,j \geq 0\}$. Using the pumping theorem, prove that $L$ is not context-free. I really don't know where to start, ...
-1
votes
1answer
59 views

What is the minimum type of logical system that recognizes if a formalized sentence is a well-formed formula thus reducible to the boolean value?

The formula, in the old way of using it, can contain symbols in order and a mixture that does not meet the criteria of correctness (i.e. arbitrary symbols do not form a well-formed formula (WFF) and ...
-1
votes
1answer
70 views

How construct PDA to $L = \{x \in(a,b,c,d)^* \mid -10 \leq ( |x|_a + |x|_b) - ( |x|_c + |x|_d) \leq 10 \}$

$L = \{x \in(a,b,c,d)^* \mid -10 \leq ( |x|_a + |x|_b) - ( |x|_c + |x|_d) \leq 10 \}$ I don't have any idea. Can someone help me.
-1
votes
1answer
54 views

Regular Expression Building

I'm having trouble constructing a regular expression to meet the following criteria: $$\sum = \{0,1\}$$ $$\epsilon \in L$$ $$0 \in L$$ $$1 \in L$$ $$\forall x \in L, 110x \in L \land x01 \in L$$ ...
-1
votes
1answer
3k views

Describing language generated by grammar

S -> aSb | A | B A -> aS | a B -> Sb | b is this the language generated by this CFG? Or am I missing something?
-2
votes
1answer
49 views

CFG for $\{uvw \mid u,v,w \in\{0,1\}^*,|u|=|v|=|w| \wedge u\neq w\} $

$L=\{uvw \mid u,v,w \in\{0,1\}^*,|u|=|v|=|w| \wedge u\neq w\} $ Any help would be appreciated.
-2
votes
1answer
343 views

Turing machine on input w tries to move its head past the left end of the tape

Consider the language $$ L = \{ \langle M,w \rangle \mid \text{$M$ on input $w$ tries to move its head past the left end of the tape}\}. $$ Prove whether L is decidable or not. I tried to prove ...
-2
votes
1answer
412 views

Kleene star of L

$L^*$ is the kleene star of L. say we have a def: $L^*$ = $L^0$ U $L^1$ U $L^2$ U ... U $L^K$ then prove that: $L^*$ = $L$ if and only if $L$ = $L$ o $L$ how do i prove this?
-2
votes
3answers
2k views

DFA for every run of a's=2 or 3

I am trying to create a dfa for L={w: every run of a's has length either two or three} this is my attempt at the solution..i feel like I am missing something..?
-2
votes
1answer
357 views

Prove that $(L^*M^*)^* = (L\cup M)^*$

I would like to find out how to prove this statement. Thank you. Well I think that I proved one part of the statement, but my proof doesn't really look elegant. My proof of $(L\cup M)^* \subset (L^*M^...
-2
votes
1answer
13k views

Regular expression for all strings with at least two 0s over alphabet {0,1}

My answer : (0+1)* 0 (0+1)* 0 (0+1)* Why is this incorrect? Can somebody explain to me what the correct answer is and why?
-3
votes
1answer
54 views

Minimization of automata with dead state

I am supposed to minimize the following DFA automa, which contains dead state: But after the minimization of the automata, it stayed the same. Is it correct?
-3
votes
1answer
185 views

Prove that TM does not decide this language

So my problem is how can I show that this TM does not decides this language. $$L = \{a^nb^nc^n\ |\ n \geq 0\} $$ It might be a basic problem and seem silly to you but still I do not know how to ...

1 2 3 4
5