Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques

learn more… | top users | synonyms

0
votes
2answers
122 views

Prove the language $\{a^k b^l : k \neq l \}$ is not regular

Prove that the following language is not regular: $$L=\{a^k b^l : k,l \ge0, k\ne l\}$$ The problem is that I should use "distinguished states" not the pumping lemma, which is usually used for such ...
0
votes
1answer
47 views

Proof by pumping lemma

Let's say that we have to prove that $L = \{ww^Rv |w,v\in \Sigma^*\}$ is irregular. I would take a string such that $w = baba^m$ and $w^R=a^mbab$ and $v = a$ and then I would pump divide $w$ into ...
1
vote
1answer
24 views

Showing that all regular languages are closed under reversal

I'm trying to show that $L^{reverse} = \{w^{reverse}:w \in L\}$ is a regular language. The first argument I can come up with is simply: if we have an NFA for $L$, then an NFA for $L^{reverse}$ can be ...
4
votes
1answer
59 views

Proving that a language is not context-free

Given the language $$L = \{ a^p \mid p\, \text{IS NOT prime} \}$$ is $L$ Context free? If not, prove that it's not. May I have some suggestions on how to use the pumping lemma to prove this, ...
2
votes
1answer
42 views

A correct proof for this pumping lemma example?

Given the language $L = \{0^{2^n} | n \geq 1\}$ So, the language contains all strings that have $2^n$ $0$s. First of all I take $z = a^{2^p}$ where $p$ is the constant guaranteed by the pumping ...
4
votes
2answers
102 views

Have action/predicate systems (or similar) been considered in the literature?

Question. Has the following concept, or anything similar, been considered in the literature? Definition. An action/predicate system consists of sets $A$ (the actions) and $X$ (the predicates) such ...
0
votes
1answer
25 views

If the language is context free?

i believe intuitively the following language is CF. But there is a book (without more description) that states the language is not CF. If I'm in a wrong way? $L=\{W_1cW_2 | W_1,W_2 \in (a+b)^* W_1 ...
1
vote
2answers
65 views

The halting problem for tapes that are or are not completely blank

Is it possible to construct a Turing machine that halts only if the tape is not completely blank? Also, is it possible to construct one to halt if the tape is completely blank? Intuitively, I think ...
0
votes
2answers
81 views

Combining two DFAs into an NFA to recognize concatenation

Suppose we have two separate DFAs that each recognize their own language. What is the most efficient way to combine these two DFAs into one NFA that recognizes the concatenation of both languages?
1
vote
1answer
51 views

How to construct a grammar G such that L(G)={x^ny^mx^my^n/m,n>1}?

construct a grammar $G$ such that $L(G)=\{x^ny^mx^my^n/m,n>1\}$? I don't have much idea how to approach this one. Could some help me to understand how to approach these kinds of problem?
0
votes
2answers
316 views

Regular expression and DFA/NFA questions

If a language L is generated by a regular expression, then L is recognized by a DFA. I think this is true, because regular expressions describe regular languages, those of which are exactly ...
1
vote
2answers
88 views

Why is a 3-PDA no more powerful than a 2-PDA?

A k-PDA is a pushdown automata with k stacks. My textbook on Computation Theory has an exercise that asks to prove that 3-PDA is no more powerful than a 2-PDA. Now consider the language that I made ...
3
votes
1answer
43 views

Proof of a Known Claim About Languages

I would like to know how to prove that there is no non-trivial language $L$ that satisfies the following condition: $${\large \left(\overline{L}\right)^* = \overline{L^*}}$$ "Non-trivial" is ...
0
votes
1answer
20 views

Reversed Language of a Non Regular Language

Is the following saying true or false? In any case why? Thanks!
2
votes
1answer
57 views

Context free grammar for language

I'm learning how to generate context-free grammar for a language. $L=\{{a}^i {b}^j {c}^k\, |\,i=j\lor j=k$ Here is how I tried ...
0
votes
2answers
36 views

What method should you follow to show what a DFA does?

I'm specifically looking for help analyzing the following DFA. What steps would one follow to show what language this particular DFA accepts? To me it seems quite random, and I can't figure out a ...
1
vote
2answers
54 views

Reduction between two languages and a common one

My question is as following : Let $A$ and $B$ be some languages, there exist a language $C$ such that $A\le C$ and $B\le C$, where "$\le$" means "reducible to", so $A\le C$ means there is a mapping ...
0
votes
2answers
35 views

Determining a language with a Turing Machine

How can I build a Turing Machine that determines the following language? $$L_{E - DFA} = \{\langle A \rangle | \text{$A$ is a $DFA$ and $L(A) = \varnothing$}\}$$ Thanks alot
0
votes
1answer
77 views

Why isn't this a sufficient proof?

So basically, we have a question that asks us to prove that given a particular Deterministic finite automaton (DFA), there is a symbol for which we can get to a state $q$ from a state $p$ given a ...
0
votes
3answers
21 views

If $s \geq 3$, $3$ divides $s$, and $t = s/3$, then $t+1 < s$.

I am using the pumping lemma to prove a language is not regular, and would like to assert what I have stated in the title of the question to complete my proof. That is, if $s \geq 3$, $3$ divides $s$, ...
1
vote
3answers
82 views

NFA for $(ab|a)^{*}$ using only 2 states

In Introduction to the Theory of Computation by Michael Sipser, there's an example which shows how to convert the regular expression $ (ab|a)^{*}$ into an NFA. The "standard" method results in 8 ...
1
vote
1answer
53 views

Is the PDA I drew correct?

Could you tell me if the language $L=\{a^{m}b^{n}:m \neq n,m>0,n>0 \} $ is accepted by the following pushdown automaton, where the alphabet of the stack is $\{a,z\}$ and $z$ is the initial ...
1
vote
0answers
46 views

Theory of Automata concepts

I just started taking Theory of Automata and I'm having a hard time understanding some of the concepts. It's been only a week and the following questions are my homework. I'm not asking you to do my ...
2
votes
1answer
59 views

Prove that RE is closed under reduction

Prove that the class RE is closed under reduction. Definitions: A language $ A \subseteq \Sigma^*$ is called reducible to $ B \subseteq \Gamma^*$ ( denoted by $A \leq B$) if there is a computable ...
1
vote
1answer
37 views

Languages that are not comparable in $R$

I want to know if there are $2$ languages $A,B\in{R}$ such that there's no reduction between them. Namely, $2$ languages $A$ and $B$ $\in$ $R$ such that $A\not\le B$ and $B\not\le A$ Thanks a lot!
0
votes
2answers
52 views

Determining whether a language belongs to R or RE (Turing Machines)

Does the language L belong to R, RE or neither? In each case, why? Thanks a lot!
1
vote
1answer
47 views

is this language regular or not?

I have problem with this language $$L = \{ a^n b^m : \text{$n+m$ is odd} \}$$ is it regular or not My Solution I used pumping lemma, w = a^2p b^2p+1 (the same for a^2p+1 b^2m ) ...
1
vote
0answers
44 views

Extended PDA vs TM

We studied in class that PDA is less powerful than TM. My question is: Extended PDA : for every $\alpha,\beta \in \Gamma \cup \{\epsilon\}$, $\sigma \in \Sigma \cup \{\epsilon\}$, $q,r \in Q$, $w ...
0
votes
1answer
69 views

Finding regular expressions

I'm given the DFA shown below and need to find regular expressions for the following languages: $L_{1,2}^0, L_{2,1}^6, L_{2,5}^4, L_{2,3}^5, L_{1,3}^5$. The language $L_{p,q}^r$ is defined as ...
4
votes
2answers
79 views

Showing that 2 languages are context free

I have these 2 languages: $$L_1 = \left\{a^ib^jc^k: k\ge i+j\right\}\\ L_2 = \left\{w_1cw_2 : w_1,w_2\in\{a,b\}^\ast\land |w_1|_a = |w_2|_a\right\}$$ How can I determine that they are context free ...
-1
votes
0answers
121 views

Up-Down Automaton

I've been give this question, about Pushdown Automata. they defined a new Automata, up down automata, as followed- it has all options a regular Automata has, but : and for each: now I need to ...
1
vote
1answer
76 views

Push down automata for context free grammar

I'm having trouble finding the PDA for this language $L = \{x^{3i} y^j z^k\ |\ i \ge 0 \land k \gt 2j \gt 0\}$ The ...
1
vote
0answers
42 views

Language requiring a DFA with a certain number of states to implement

For any function $f\colon\{0,1\}^n\to\{0,1\}$, define a language $S_f = \{(b_1,b_2,\ldots ,b_n)\in\{0,1\}^n : f(b_1,b_2,\ldots ,b_n) = 1\}$. So all words in the langugage has same length $n$. I have ...
2
votes
1answer
55 views

(Transformation) Semigroups, the semigroup $\mathbf D_n$ and the wreath product

I have some trouble understanding the following proof, were I can't even figure out how some terms are defined. But first I state some definitions and preliminary lemmas. A transformation semigroup ...
0
votes
1answer
113 views

Prove that a PDA with accept states accepts all context-free languages

Or in other words that $\forall L: L \in DCFL => L \in CFL$. First of all, does this statement even require a proof? My idea was to let L be an arbitrary language, such that $L \in DCFL$, this ...
0
votes
1answer
45 views

build finite automaton for language minimize states

I want to build a finite automaton that accepts $a^nb^n, n \gt 0, m \ge 0$. I can't do it unless the FA has two final states, i.e.: $delta(q0, a) = q1 delta(q1, a) = q1 delta(q1, b) = q2 delta(q2, ...
1
vote
1answer
165 views

DFA for Boolean Formula

Let $ f\left( b_{1}, \dots , b_{n} \right)$ be a boolean function. Define $S_{f} = \{\left( b_{1}, \dots , b_{n} \right): f\left( b_{1}, \dots , b_{n} \right)=1; b_{i} \in \{0,1\}, 1\leq i \leq n \}$ ...
4
votes
1answer
367 views

The shortest word in context free language

Let $G=(\Sigma,N,R,S)$ be a context-free grammar. For every production rule A --> w, we say that its length is $r$ if $|w|=r$. In addition $n = |N|$, and $k =$ the maximal length of a production rule ...
0
votes
1answer
31 views

Help Specify possible definitions for this Boolean Function

My math is rusty, but I need some guidance here. Problem I wish to design a stochastic, boolean procedure $f(state)$, that picks a winner, $f(state_{win})\to 1$ or loser, $f(state_{loss})\to 0$. I ...
0
votes
0answers
25 views

Is the next expression true: $(L_1 \cap L_2 )L_3\subseteq L_1L_3\cap L_2 L_3$?

Let $L_1,L_2,L_3$ be languages, Is the next expression true: $(L_1 \cap L_2 )L_3\subseteq L_1L_3\cap L_2 L_3$? After a half an hour of trying to disprove it, I've decided my intuition might be wrong. ...
1
vote
0answers
88 views

Oracle Turing machine - $E_{\text{TM}}$ and $PCP$.

$$E_{\text{TM}}=\{\langle M\rangle|M\text{ is a TM and $L(M)=\emptyset$}\}.$$ $E_{\text{TM}}$ is undecidable $$PCP=\{\langle P\rangle|P\text{ is an instance of the Post Correspondence Problem with a ...
3
votes
1answer
33 views

Irregular $a^nb^n$

We studied in class that regular languages closed under intersection. My question is : if we take the irregular language $L =$ {$a^nb^n : n\geq 0$} and the regular finite language $L' = \{a^3 ...
2
votes
1answer
48 views

Reducing A$_\text{TM}$ to REGULAR$_\text{TM}$

We can solve A$_\text{TM}$ problem using REGULAR$_\text{TM}$. Assume $R$ is a Turing machine that decides REGULAR$_\text{TM}$. We construct $S$ to decide A$_\text{TM}$ as follows On input ...
2
votes
1answer
50 views

Language concatenation

We learned in class that the regular languages are closed under concatenation (e.g $L_1L_2 =\{ w_1w_2 : w_1 \in L_1,w_2 \in L_2\}$ is a regular language if $L_1$ and $L_2$ are also regular ...
1
vote
2answers
101 views

Proving $L=\{0^n \mid \text{n is a perfect square}\}$ is not a Regular Language without the Pumping Lemma

Is this a valid way of going about proving the proposition? Let $L = \{0^n \mid \text{n is a perfect square}\}$. The regular languages are closed under concatenation. So if $x \in L, y \in L$, then ...
2
votes
1answer
82 views

DFA Rejection State

I'm being asked to construct a DFA for the language over $\{0,1\}$ such that each string of five consecutive symbols contain at least two zeroes. In my construction, it seems to me that it would make ...
0
votes
1answer
18 views

proving regular language

let $L$ be a language over the alphabet $\{a,b\}$ that maintains that for each $w \in L$ ,the difference in absolute between the number of apearences of the letter $a$ and the number of apearences ...
1
vote
1answer
54 views

Grammar outside the Chomsky Hierarchy

This grammar describes a language that may fall outside the Chomsky Hierarchy (CH): \begin{array}{l} S \to abAbba \\ A \to abA \mid bbaB \\ B \to aab \\ \lambda \to Aab \mid aB \\ \end{array} Going ...
1
vote
1answer
39 views

Consider this grammar

Consider this grammar: \begin{array}{l} S \to aabBba \mid aAb \mid aab \\ bBb \to bCa \mid aaa\\ aA \to aC \mid bba\\ C \to aab \mid Cb \end{array} This is clearly context-sensitive (CS). It's not ...
0
votes
0answers
35 views

Context-sensitive grammar for this language

In order to write a context-sensitive grammar for: $L = \{ a^{n} b^{n} c^{n} d^{n} : n \ge 1 \}$ One possible set of productions is: $S \rightarrow aBCd | abcd $ $aB \rightarrow aaBb | ab | ...