Questions related to formal languages, grammars, and automata theory

learn more… | top users | synonyms (1)

0
votes
1answer
61 views

closure property on languages

The above image, taken from planetmath.org, describes the closure property on REG (regular), DCFL (deterministic context-free), CFL (context-free), CSL (context-sensitive), RC (recursive), RE ...
0
votes
1answer
55 views

Union of finite and non-regular language [duplicate]

Question: ($B$ and $C$ are languages) $B$ is finite,$C$ isn't regular: Prove/Disprove: $C\cup B$ isn't regular. Thoughts: My intuition says this is true, but I need an idea to prove it. Since I ...
0
votes
1answer
56 views

Three languages and how to decide if they are regular [closed]

From following languages which one is regular and why others are not?And what is the regular expression for regular one. $L_1= \{wxwy | x,y,w \in (a+b)^+\}$ $L_2 = \{xwyw | x,y,w \in (a+b)^+\}$ ...
4
votes
1answer
70 views

Is there $L$ such that $L$ and $\bar L$ are context free, but $L$ is not deterministic context free?

The usual candidates for context free languages whose complement is also context free, but they are not regular are the Deterministic Context Free Languages ($DCFL$). For example, $L=\{a^nb^n\mid ...
2
votes
1answer
353 views

Reducing a non-RE language to its complement

Is there a language $L$ such that both $L$ and $L$'s complement are non turing recognizable languages, but there is a reduction between them? I couldn't find one...
-1
votes
1answer
56 views

Create CFG and pushdown automaton for {ww} [duplicate]

I've been trying to make a CFG, a pushdown automaton and a regular expression for the language $\qquad L(M) = \{ww : w \in \{a, b\}^*, |w| \text{ is even}\}$. I understand how the reverse of the ...
-1
votes
1answer
38 views

Deciding Countability of Languages

Suppose we have given $\Sigma=\{a,b\}$, Which one of the following set is not countable (a) Set of all languages over $\Sigma$ (b) Set of all regular languages over $\Sigma$ (c) Set of ...
0
votes
1answer
46 views

What context free grammar generates the language $L(G) = \{a^ib^jc^{2i}d^m\}$ [duplicate]

I am struggling to think of the context-free grammar that generates the language $L(G) = \{a^ib^jc^{2i}d^m\}$, where $i$, $j$ and $m$ are natural numbers. Also, in general, are there any good methods ...
-1
votes
2answers
98 views

Pushdown Automata: CFG to PDA

I have the following grammar for a context-free language: $G = (\{S,A,B\}, \{x,y,z\}, P, S)$ with $P = \{S \rightarrow A, A \rightarrow xAz, A \rightarrow xBz, B \rightarrow y\}$ My question is: How ...
0
votes
0answers
36 views

$L = \{x\#x^R \mid x\in\{0,1\}^* \} $ not accepted by a queue automaton?

It can be proven that class of languages accepted by queue automata is equal to class of languages accepted by Turing machines. It was mentioned somewhere that the language $$L = \{x\#x^R \mid ...
0
votes
0answers
50 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 ...
1
vote
0answers
115 views

Is the complement of this language Context-Free $\{(a^nb^n)^m \mid n>0,m>0\}$?

I've been asked to decide whether a given language is a Context-Free Language (CFL). If yes, I should find the grammar that creates her, and if not, I need to prove it (with the pumping lemma). The ...
0
votes
2answers
45 views

what is the best way to approach the construction of nondeterministic PDA's?

I'm trying to construct a PDA for $L = \{w0^i1^j \mid w\text{ ends in } 01 \wedge 2i=3j\}$. My understanding is that I have to first accept an arbitrary number of zeros and ones and then ...
1
vote
1answer
69 views

Kleene star and Kleene plus

Let $\Sigma$ be an alphabet. Have a look at following definitions frequently used in literature containing Kleene star and Kleene plus. $\Sigma^* := \Sigma^+ \cup \{\varepsilon\}$ $\Sigma^+ := ...
0
votes
2answers
46 views

Kleene closure, concatenation problem

If $L_1 = \emptyset$ , $L_2= \{a\}$ then what is $$L_1\cdot L_2^* \cup L_1^*$$ The answer given is $\{\epsilon\}$ but I think it should be $\{\epsilon,a\}$. My Approach : $L_1^* = \{\epsilon\}$ ...
5
votes
2answers
87 views

Languages of cardinality higher than $\aleph_0$

I was studying model theory and that's how I came across formal languages. I looked around but it seems as though a language (set of strings over some alphabet) is usually treated as being finite or ...
0
votes
1answer
29 views

If $L$ is a $CFL$, then why isn't $L^*$ also $CFL$

I was studying closure properties of CFLs and I came across this. I want to understand why $L^*$ is not a CFL, can anyone explain me in depth with simple examples?
-1
votes
1answer
20 views

Language equivalence proof [duplicate]

Can anyone explain to me how the following is true for any language? $$L^+ = LL^* = L^*L$$ I'm confused because $L^*$ is the set of all words including the empty string, while $L^+$ is the set of ...
0
votes
1answer
41 views

Give an example of a non-regular language $L$ such that $L^*$ is regular [duplicate]

I can't think of an example of a non-regular language $L$ such that $L^*$ is regular. . Any help ?
2
votes
1answer
92 views

Language of binary strings divisible by 7

There was a question something like, "Consider the language of all integers converted to binary form. The language of all strings divisible by 7 is : 1) Recognizable by a finite-automaton. 2) ...
2
votes
1answer
25 views

Can a language recognized by a NFA be recognized by a push down or Turing machine?

Every single NFA has an equivalent DFA representation so that every language recognized by NFA is recognized by the DFA, but is it also true that the language recognized by NFA is recognized by a push ...
2
votes
0answers
52 views

Morse code is a ternary human-optimised code, is there a binary, non-machine optimised code? [closed]

Is Morse code without spaces uniquely decipherable? Discusses how Morse code isn't very clear without the third (usually) unseen element, the space. Is there a (historical?) human-optimised (vs. ...
1
vote
2answers
103 views

PDA recognising all strings with a $1$ in the second half

My professor gave us an old exam to look over for our final exam and I am having a hard time understanding the push down automata problem he gave. In the problem it says: Let $\Sigma = \{0,1\}$ ...
6
votes
2answers
2k views

Is 0* decidable?

I found a statement (without explanation) that a language $A = 0^*$ is decidable. How is that possible? I mean, how would we build a Turing machine that would accept (or reject) a possibly infinite ...
2
votes
1answer
71 views

Finite Automata — Determine if a set is regular

I have been at this for hours. The question is: Prove that the language $A = \{0^kx \mid k > 0, x \in \{0,1\}^*, \text{ and } \#(0,x) \geq k\}$ is regular, where $\#(n, x)$ denotes the ...
3
votes
2answers
77 views

Decide if this language is context free

I got this question for homework: Decide if this language is context free or not: $\qquad \{x@1^m: x \in \left\{0,1\right\}^*, m \in \mathbb{N}, x_m = 1\}$. Intuitively I think it's not ...
4
votes
1answer
53 views

Do an ambiguous grammar and its corresponding unambiguous version generate the same language?

If I have an ambiguous grammar G and its disambiguated version D. Then which one is true L(D) ⊂ L(G) , L(G) ⊂ L(D) or L(G)=L(D)? As I tried with some examples to transform a grammar to it ...
1
vote
1answer
74 views

Turing Machine for strings without bbb

I am trying to generate a transition graph for a turing machine that accepts the languages of all strings that do not contain the substring $bbb$ with the input alphabet $\Sigma = \{a, b\}$. When I ...
2
votes
1answer
124 views

are regular languages closed under division

I am trying to solve this question which appeared in previous exam paper Can someone help me what i am failing to understand For languages $A$ and $B$ define $A \div B = \{x \in \Sigma^{\ast} : xy ...
6
votes
1answer
261 views

Parikh's Theorem: CFL's “contain” regular languages?

The first sentence of the Wikipedia article for Parikh's Theorem states: "Parikh's theorem in theoretical computer science says that if one looks only at the relative number of occurrences of ...
2
votes
1answer
108 views

regular expression for binary language has at least one 1

So I had an exam in the subject "Theory Of Computation" and one of the questions was to write down a regular expression of a binary language that has at least one (1) , my answer was : 0* 1 0* (0* 1 ...
2
votes
1answer
63 views

How to prove that the Myhill-Nerode equivalence classes for L are the same as for its complement?

Given language $L$, I want to show that its Myhill-Nerode equivalence classes are the same as for its complement $\overline{L}$. I am thinking of constructing a DFA $M$ for the Language $L$ so the ...
1
vote
1answer
94 views

Is Myhill-Nerode equivalence class of a language which contains all palindrome pairwise distinct?

In my formal language class, we define a language called PAL, which is on a alphabet set $\Sigma = \{0,1\}$. $PAL = \{w \in \{0,1\}^* : w = w^R\}$. We have proved that every string in this language ...
3
votes
2answers
97 views

Can every context free language written as a intersection of another context free language and a regular language?

I'm preparing an Formal language exam, One question from previous year's final is: Prove or disprove:If L is a context free language, then there exists a language P that is generated by a pure ...
1
vote
1answer
144 views

Reducing context-free languages with polynomial-time reductions

So, let's say we have two languages $L$ (which is any context-free language) and $M$ which is the basic CFL $\{0^n1^n: n\geq 0\}$. Can $L \le_p M$ ? Why or why not? How do polynomial time reductions ...
2
votes
3answers
120 views

How to generate a context sensitive grammar

I am trying to solve for my exam coming up and have no clue how to generate the grammar for Context sensitive languages for example how do i proceed on this kind of question. Give a context-sensitive ...
1
vote
2answers
207 views

What's the definition of a (deterministic) formal language?

Definitions According to my UML teacher formal means strictly according to rules, officially and how it's supposed to be. He says a formal language = syntax + symbols + spelling. Another term he uses ...
0
votes
1answer
32 views

prove decidability and recognizability

I want to prove that for any language $L_1$ described by a Turing machine and any regular language $L_2$, $L_1 \cap L_2$ is described by a Turing machine that its recognizability and decidability is ...
3
votes
1answer
139 views

Complexity Classes (P, NP) vs Language Hierarchies (REC, RE)

Is there any relation between the Complexity Classes (like P or NP) and Language hierarchies (like REC or RE) ? Form what I understand: (easy things are the things that can be done in polynomial ...
2
votes
1answer
22 views

How to apply “verification” and “decision” for the SUBSET SUM problem?

The SUBSET SUM problem states that: Given finite set S of integers, is there a subset whose sum is exactly t? Can someone show me why verification is simpler ...
3
votes
3answers
263 views

How to represent whitespace in a context-free grammar?

Say we want to support: xx The following grammar does accept it: S -> xAx A -> ε. because S => xAx => xx. But what about supporting: x x I realize this might be a stupid question but I'm ...
4
votes
2answers
81 views

Prove or disprove: L^2 context free implies L is context free

Clearly we have to disprove this. But I am finding it hard to prove it. I was trying in following way: Considering any non context free language L. I was trying to prove that L^2 is context free which ...
0
votes
1answer
39 views

Given family of grammars, determine if LR(k)

Parsing family of grammars, determine if LR(k) I have the exact same problem, but my reputation is not enough to comment on that thread, plus the OP hasn't been online in 2 years so I can't ask him ...
-1
votes
1answer
75 views

Proving correctness of a CFG by induction on length of strings generated [duplicate]

Consider the following grammar with starting symbol of $S$. $$S \rightarrow 0S11\;|\;S1\;|\;0$$ Let $L = \{0^i1^j:\; \ge 1\; and\; j \ge2i-2\}$ . Give a formal proof of the following claim : For all ...
0
votes
0answers
49 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 ...
1
vote
1answer
47 views

If pref(L) is regular, does that imply L is regular?

I have this exercise for homework: Say we have a language L. we know that the language pref(L) (all the prefixes of ...
1
vote
1answer
56 views

How to prove that this is NP complete?

I'm trying to prove that if P = NP, then {⟨a, b, c⟩ : a + b = c} (as addition over N) is NP-complete. I think I managed to prove that it is in NP, but I'm not sure what would be a good NP complete ...
3
votes
1answer
138 views

Question regarding Cook-Levin theorem proof

I know a key part of the Cook-Levin theorem proof (as presented in the book by Sipser) is that given two rows of configurations, if the upper row is a valid configuration of a nondeterministic Turing ...
3
votes
1answer
106 views

How to convert a grammar with finitely many ambiguous strings into a new, unambiguous grammar?

Suppose $L$ is an infinite CFL, and $G$ is a grammar with finitely many ambiguous strings which generates $L$. Is it possible to convert $G$ into an unambiguous grammar which also generates $L$? If ...
2
votes
1answer
62 views

What is one method used to prove each palindrome is in its own Myhill-Nerode equivalence class?

I understand how you can use a contradiction in regard to a DPDA to show a language has finitely many Myhill-Nerode equivalence classes, but what is the method used to show each string of a language ...