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

learn more… | top users | synonyms

1
vote
1answer
92 views

How to formally describe this Uppaal automata?

I have the following simple automata: What I'm looking for is a formal description of this based on the definition here $A=(\Sigma,\Gamma,S,s_0,\delta,\omega, F)$ How to declare all the ...
1
vote
2answers
578 views

NFA to DFA conversion, half the power set

Is there a way to tell when a NFA will use at least half the power set when converted to a DFA. I tried to create a few examples, but i just can't see a pattern that would say whether an NFA will use ...
0
votes
1answer
141 views

Difference between $(a|b)^\ast$ and $a^\ast b^\ast$?

What is the difference between $(a|b)^\ast$ and $a^\ast b^\ast$? Can you show more examples of Kleene star and patterns and explain a little bit? I've searched so many sites in Google, but it returns ...
0
votes
3answers
191 views

Word problem in a free group

Can the word problem in a free group be solved by a finite state automaton? I know it can be solved by a pushdown automaton.
0
votes
3answers
674 views

Are these languages context free or not?

$L_1=\{a^nb^mc^nd^m \mid m,n >0\}$ $L_2=\{a^nb^mc^md^n \mid m,n >0 \}$ $L_3=\{a^mb^n \mid m+n\text{ is a prime number}\}$ $L_4=\{a^mb^n \mid n=m^2\}$ $L_5=\big\{ww^R\#ww^R \mid w \in \{a,b\}^* ...
0
votes
2answers
145 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
2answers
141 views

regular expression

I would like to write the regular expression for the set of all binary strings where there are no three consecutive 0's. The following strings are part of the language: ...
0
votes
1answer
133 views

Decidability of a Turing machine always halting in at most ten steps

I've exam comping up soon and I need help with this. Consider the problem: Given a Turing machine $M$, determine if $M$ halts in at most ten steps on every input. Is this decidable? Prove your ...
0
votes
3answers
82 views

Is this DFA correct for the language $\{w \mid w \in \{ab\}^*\}$?

Language: $\{w \mid w \in \{ab\}^*\}$
0
votes
1answer
255 views

Properties of a valid DFA

Is a DFA required to have transitions on each input symbol from each state defined? If there isn't a path from state q1 to another state on input a for example, does that invalidate the DFA itself. ...
0
votes
1answer
343 views

Is it always possible to convert a non-deterministic PDA to a deterministic one?

Is it always possible to convert a non-deterministic PDA to a deterministic one? What is the significance of this observation for the computing power of contex-free grammars?
0
votes
3answers
162 views

What is the difference between regex operations in math and regex in UNIX / Linux?

What is the difference between regular expression operations (union, concatenation, kleene star) and regular expression (implemented in UNIX and can be used together with the grep command)? Are there ...
0
votes
1answer
53 views

Determine whether $L=\{w:|w|_a=2^n+273\text{ for }n\in \mathbb{N}\}$ is regular.

Given the alphabet $\Sigma=\{a, b\}$ and for the next Language $L=\{w:|w|_a=2^n+273\text{ for }n\in \mathbb{N}\}$ determine whether the language is regular. Firstly, I think this language is regular. ...
0
votes
2answers
44 views

Subset of A Regular Language

I need to show that a subset of a regular language is regular or not. I think it may not be regular but I could not find a counter example. Do you have any simple example to prove that? Thanks in ...
0
votes
1answer
267 views

An infinite context free language can be split into two infinite regular languages

Prove or disprove Let $L$ be an infinite context free language. Show that there exists a regular language $R$ such that $ L \cap R $ and $L \cap \overline{R} $ are infinite and regular.
0
votes
1answer
140 views

Number of states required for deterministic finite automata

Lemma in text: Let $c$ be a constant and $L = \{1^c\}$ (the singleton language containing the string of $c$ many 1's). Then no DFA with < $c$ states can accept $L$. The given proof assumes ...
0
votes
2answers
38 views

Confusion related to a property of languages on some alphabet V

I came across this relation betwen tww sets of languages formed from the alphabet V. A,B The relation is $$ A^*\cup B^* =((A\cup B)^*)^* $$ I am confused how this is derived. Any pointer?
0
votes
2answers
20 views

Language of Grammar

Let $G = (V,T,S,P)$ be the phrase structure grammar with $V = \{0,1,A,S\}$, $T=\{0,1\}$, and a set of productions $P$ consisting of: $S \to 1S$ $S \to 00A$ $A \to 0A$ $A \to 0$ What is the ...
0
votes
2answers
51 views

Construct a PDA to accept the language

construct a PDA that accepts the language: a) $L_1 = \{ a^k b^k c^i \mid k,i \ge 0 \}$ my answer is : $$\begin{align*} &S\to AA\\ &A\to abc \mid ab \mid c \mid \lambda \end{align*}$$ b) ...
0
votes
2answers
55 views

How to design a Context-Free Grammar and Pushdown Automaton for the following language:

How would you design a context-free grammar for the following language? $\{p^n \ r^m \ p \ \ b^{m+n} \ \ r^2 ∣ m,n\geq 0\}$ Derive a Pushdown Automaton that accepts the same language as the CFG. ...
0
votes
1answer
41 views

Deterministic finite automaton algorithm

I am having a little trouble understanding this question. For a DFA M = (Q, Σ, δ, q0, F), we say that a state q ∈ Q is reachable if there exists some string w ∈ Σ∗ such that q = δ∗(q0, w). Give an ...
0
votes
1answer
68 views

CFG and PDA for w1#w2

Looking for a Context Free Grammar and Push Down Automata to describe a language made of two words, separated by a #, where the first words is not equal to the second word. For this example, we can ...
0
votes
1answer
52 views

Deterministic finite automata [closed]

For this question about Deterministic finite automata: Is this answer: bbbb, bbba, bbab, bbaa, b, a correct?
0
votes
2answers
26 views

Regular Expression Similarity Check

I was solving Formal Language and Automata Theory for a competitive exam, whence I came upon this following question: The regular expression 0*(10*)* denotes same set as: 0(0+10)* (0+1)10(0+1) ...
0
votes
1answer
96 views

Turing Machine Problem

We know, A Turing machine is a hypothetical device that manipulates symbols on a strip of tape according to a table of rules I Draw a TM for input $x=(0+1)^*$ i want to implement ...
0
votes
1answer
66 views

Challenge on Property of Complement in Language

We have: and M be a finite automata. Suppose d(M) be a deterministic automata that equivalence to M. if $M_1$ and $M_2$ be two finite automata, $M_1 + M_2$ is the finite automata such that the ...
0
votes
1answer
60 views

What does q-prime ($q'$) actually mean?

I'm learning about finite automata right now, and struggling with a bit of the math notation. In the explanation here: http://math.stackexchange.com/a/563875/125649, the user explains that the ...
0
votes
1answer
82 views

Prove or disprove that the language $L_1 = \{a^nb^m \mid n < m \}$ is regular

I have possible strategy for a proof that it is not regular. I am wondering if it is valid. Step 1: Prove that the language $L_2 = \{a^nb^n\}$ is not regular (for example with the Pumping Lemma). ...
0
votes
2answers
33 views

Proof that suffix of $ab$ needs at least 3 states in NFA

I need to prove that for an NFA that accepts all languages $L(M)=\{w \in \{a,b\}^* \mid wab \}$ with a suffix of $ab$ needs at least 3 states. The smallest automata would look like this: $\to(s) \to ...
0
votes
1answer
31 views

Create a general NFA for $M_n$

I need to create a general NFA $M_n$ where $n \in \mathbb{N_0}$ with the following language defined: $$L(M_n) = \left\{ w \in \{0,1\}^* \big | x1y \textit{ for } x \in \{0,1\}^* \textit{ and } y \in ...
0
votes
2answers
81 views

Turing machine true/false questions

There is a non-regular language that is recognized by a Turing Machine. I believe the answer to this is true, because Turing machines can "count" computations and ...
0
votes
1answer
49 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 ...
0
votes
2answers
38 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
78 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
26 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$, ...
0
votes
1answer
169 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
20 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 ...
0
votes
1answer
40 views

Question about second condition of pumping lemma

I don't think that I fully understand how to use the pumping lemma to prove that a given language is not regular. I'm reading Sipser and according to him the definition of the pumping lemma is: "If A ...
0
votes
1answer
53 views

Showing a grammar to be ambiguous

I'm learning about grammar ambiguity and trying to show the following grammar is ambiguous: $S \rightarrow ScS | SdS | A$ $A \rightarrow a | b$ I used 2 different left-derivations to get the same ...
0
votes
1answer
118 views

Grammar into Chomsky Normal Form

Convert the following grammar into Chomsky Normal Form (CNF): S → aS | aAA | bB A → aA | λ B → bB | aaB I think this looks ok, but not sure. Maybe someone can point out where I go wrong: ...
0
votes
1answer
70 views

Construct an automaton by using sliding window method

Given alphabet $\Gamma = \{0,1\}$, let $L = \{\omega : All\ words\ ending\ 010\}$ be a language. Find an automaton. I have to find an automaton using sliding window method.. First I need some ...
0
votes
1answer
327 views

Show that a language is not regular using Myhill-Nerode Theorem

I'd like to show that the language below is not regular using Myhill-Nerode Theorem. How can I do that? Let Σ = {0, 1}. Let L = {ww|w ∈ Σ*} I am not sure where ...
0
votes
2answers
71 views

Constructing regular grammar

I'm trying to make a regular grammar for this language: $$ L = \{ a^ncb^m(cc)^p : n\ge 1, m\le 1, p\ge 0\} $$ Where the alphabet is $ \Sigma = \{a,b,c\}$ It seemed like right-linear. This may be ...
0
votes
2answers
56 views

context free grammar design

Design a context free grammar and PDA for the following language. $$\Sigma = \{0,1\},\qquad L = \left\{uv \mid u \in \sum^{*} \;v\in \sum^{*}1\sum^{*} \text{ with }|u| \geq |v| \right\}$$ I'm not ...
0
votes
2answers
58 views

$2^E$ where $E$ is a set

I'm studing the definition of automaton $G=(X, E, f, \Gamma, x_o, X_m)$ where $X$ is the set of states and $E$ is the set of events. My sources report that $\Gamma:X \rightarrow 2^E$ is the indicator ...
0
votes
1answer
58 views

Connection of closed subsets of $A^{\omega}$ and deterministic Büchi-Automata, Question from Book: Infinite Word by D. Perrin & J.-E. Pin

In the Book Infinite Words (homepage) it is proofed that: If $X \subseteq A^{\omega}$, then regarding the Cantor-Topology, the following is equivalent: (1) $X$ is closed (2) $X$ is recognized by a ...
0
votes
1answer
126 views

Proving what are the equivalence classes of the relation $R_{L}$

I tried writing a solution for a question that defined a language $L$ and asked to find the equivalence classes of the relation $R_{L}$ The TA wrote that "this is not what you should prove" (or "this ...
0
votes
1answer
53 views

Legal actions on a PDA and terminology

I am unsure about the following so I would like to verify if my statements are true: We can remove at most a single character ($Z\in\Gamma$) from the PDA (top ?) of the stack with one step of the ...
0
votes
1answer
47 views

Given two NFAs, is there a way to figure out if there exists a language that works for both of them?

Given two non-deterministic finite automaton, is there a way to determine if there exists a single language that satisfies them both?
0
votes
1answer
126 views

A question about the regular languages being closed under Boolean operation (how to generalize)

I know that if $L_{1},L_{2}$ are regular languages then so is $L_{1}\cap L_{2},L_{1}\cup L_{2}$ are regular languages, I also know that $L$ is regular $\implies L^{c}$ is regular . It is easy to ...